10.3969/j.issn.1009-3044.2009.10.041
连通支配集一种集中式近似算法
简单无向图的最小连通支配集问题是NP完全问题.目前还没有成熟解法.提出了一种用有序表构建独立集求解连通支配集的算法,算法从图中度最大的顶点开始将顶点加入到有序表中,并在加入过程中构建独立集,同时加入其他节点连接独立集使其成为连通集.当图中所有节点处理完成,有序表中标记为独立集的节点和连接节点就形成了一个连通支配集.实验表明算法生成的支配集较小,运行时间复杂度比较低.
连通支配集、独立集、集中式算法、有序表
5
TP301.6(计算技术、计算机技术)
2009-06-09(万方平台首次上网日期,不代表论文的发表时间)
共3页
2634-2635,2645