min_weighted_dominating_set

min_weighted_dominating_set(G, weight=None)

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}