连通支配集一种集中式近似算法

简单无向图的最小连通支配集问题是NP完全问题,目前还没有成熟解法。提出了一种用有序表构建独立集求解连通支配集的算法,算法从图中度最大的顶点开始将顶点加入到有序表中,并在加入过程中构建独立集,同时加入其他节点连接独立集使其成为连通集。当图中所有节点处理完成,有序表中标记为独立集的节点和连接节点就形成了一个连通支配集。实验表明算法生成的支配集较小,运行时间复杂度比较低。

Approximation centralized algorithm for connect dominating sets

The minimum Connected Dominating Set problem of simple undirected graph is NP-complete,there is no mature solution.This thesis puts forward an algorithm of Solving Connected Dominating set by using an ordered list of constructing independent set.The algo-rithm will put the vertex of the largest degree in the ordered list firstly,and in this process construct independent set,and construct connec-tivity set by connecting independent set and other vertex of joining.When all nodes are disposed,the vertex of tag...