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
 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^*)
, wherew(V)
denotes the sum of the weights of each node in the graph andw(V^*)
denotes the sum of the weights of each node in the minimum weight dominating 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^*)
, wherew(V)
denotes the sum of the weights of each node in the graph andw(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.