Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

min_weighted_dominating_set

min_weighted_dominating_set(G, weight=None)

Returns a dominating set that approximates the minimum weight node dominating set.

Parameters:

• G (NetworkX graph) – Undirected graph.
• weight (string) – The node attribute storing the weight of an edge. If provided, the node attribute with this key must be a number for each node. If not provided, each node is assumed to have weight one.

Returns:

min_weight_dominating_set – A set of nodes, the sum of whose weights is no more than \((\log w(V)) w(V^*)\), where \(w(V)\) denotes the sum of the weights of each node in the graph and \(w(V^*)\) denotes the sum of the weights of each node in the minimum weight dominating set.

Return type:

set

Notes

This algorithm computes an approximate minimum weighted dominating set for the graph G. The returned solution has weight \((\log w(V)) w(V^*)\), where \(w(V)\) denotes the sum of the weights of each node in the graph and \(w(V^*)\) denotes the sum of the weights of each node in the minimum weight dominating set for the graph.

This implementation of the algorithm runs in \(O(m)\) time, where \(m\) is the number of edges in the graph.

References

[1]	Vazirani, Vijay V. Approximation Algorithms. Springer Science & Business Media, 2001.