This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
- min_weighted_dominating_set(G, weight=None)¶
Return minimum weight vertex dominating set.
G : NetworkX 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.
min_weight_dominating_set : set
Returns a set of vertices whose weight sum is no more than log w(V) * OPT
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|)\).
[R141] Vazirani, Vijay Approximation Algorithms (2001)