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

摘要：

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

关键词：连通支配集、独立集、集中式算法、有序表

所属期刊栏目：5

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2009-06-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：2634-2635,2645