min_edge_dominating_set

min_edge_dominating_set(G)

返回最小基数边缘控制集。

参数

G网络X图表

无向图

返回

min_edge_dominating_set设置

返回一组大小不超过2*opt的主边。

笔记

该算法计算边支配集问题的近似解。就集合的大小而言，结果不超过2*opt。该算法的运行时间为 \(O(|E|)\) 。