min_weighted_dominating_set¶

min_weighted_dominating_set(G, weight=None)[source]¶

Return minimum weight vertex dominating set.

Parameters:

G : NetworkX graph

Undirected graph

weight : None or string, optional (default = None)

If None, every edge has weight/distance/weight 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1.

Returns:

min_weight_dominating_set : set

Returns a set of vertices whose weight sum is no more than log w(V) * OPT

Notes

This algorithm computes an approximate minimum weighted dominating set for the graph G. The upper-bound on the size of the solution is log w(V) * OPT. Runtime of the algorithm is \(O(|E|)\).

References

[R144]

Vazirani, Vijay Approximation Algorithms (2001)