min_weighted_dominating_set

min_weighted_dominating_set(G, weight=None)

返回一个近似最小权重节点控制集的控制集。

参数

G网络X图表

无向图。

weight字符串

存储节点权重的节点属性。如果提供，则具有该键的节点属性必须是每个节点的编号。如果未提供，则假定每个节点的权重为1。

返回

min_weight_dominating_set设置

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

笔记

该算法为图形计算一个近似的最小加权控制集。 G . 返回的溶液有重量 (log w(V)) w(V^*) 在哪里 w(V) 表示图中每个节点的权重和 w(V^*) 表示图的最小权重控制集中每个节点的权重之和。

该算法的实现运行在 \(O(m)\) 时间，在哪里 \(m\) 是图形中的边数。

工具书类

1

瓦齐拉尼，维杰五世。 近似算法 . 斯普林格科学与商业媒体，2001年。