min_weighted_dominating_set

min_weighted_dominating_set(G, weight=None)

返回一个近似的最小权重节点支配集。

Parameters:

GNetworkX 图

无向图。

weight字符串

存储节点权重的节点属性。如果提供，每个节点的该属性键必须是一个数字。如果未提供，则每个节点假设权重为1。

Returns:

min_weight_dominating_set集合

一个节点集合，其权重之和不超过 (log w(V)) w(V^*) ，其中 w(V) 表示图中每个节点的权重之和， w(V^*) 表示图中每个节点的最小权重支配集的权重之和。

Raises:

NetworkXNotImplemented

如果 G 是有向图。

Notes

该算法计算图 G 的近似最小权重支配集。返回的解的权重为 (log w(V)) w(V^*) ，其中 w(V) 表示图中每个节点的权重之和， w(V^*) 表示图中每个节点的最小权重支配集的权重之和。

该算法的实现运行时间为 \(O(m)\)，其中 \(m\) 是图中的边数。

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}