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

Approximation centralized algorithm for connect dominating sets

作　　者：李玉华[1] 刘晓庆[1] LI Yu-hua, LIU Xiao-qing （School of Information Science and Technology,SouthWest JiaoTong University,Chengdu 610031,China）

机构地区：[1]西南交通大学信息科学与技术学院,四川成都610031

出　　处：《电脑知识与技术》2009年第4期2634-2635,2645,共3页Computer Knowledge and Technology

摘　　要：简单无向图的最小连通支配集问题是NP完全问题，目前还没有成熟解法。提出了一种用有序袁构建独立集求解连通支配集的算法，算法从图中度最大的顶点开始将顶点加入到有序表中，并在加入过程中构建独立集，同时加入其他节点连接独立集使其成为连通集当图中所有节点处理完成，有序表中标记为独立集的节点和连接节点就形成了一个连通支配集。实验表明算法生成的支配集较小，运行时间复杂度比较低。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 algorithm will put the vertex of the largest degree in the ordered list firstly,and in this process construct independent set,and construct connectivity set by connecting independent set and other vertex of joining.When all nodes are disposed,the vertex of tag independent set in ordered table and connected node form a connected dominating set.The test shows that the forming dominating set is smaller and running time complexity is lower than original.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]