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:

GNetworkX graph

Undirected graph.

weightstring

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_setset

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.

Raises:

NetworkXNotImplemented

If G is directed.

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.

Examples

>>> G = nx.Graph([(0, 1), (0, 4), (1, 4), (1, 2), (2, 3), (3, 4), (2, 5)])
>>> nx.approximation.min_weighted_dominating_set(G)
{1, 2, 4}