networkx.algorithms.approximation.dominating_set.min_weighted_dominating_set

min_weighted_dominating_set(G, weight=None)[source]

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 node. 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.