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

• 作者: 刘晓庆 李玉华
• 来源期刊: 电脑知识与技术
• 学科: 工学
• 关键词: 连通支配集 独立集 集中式算法 有序表
• 年，卷（期）: 2009,（10）
• 所属期刊栏目: 软件设计开发
• 页码范围: 2634-2635,2645
• 页数: 3页
• 分类号: TP301.6
• 字数: 3429字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-3044.2009.10.041

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李玉华	西南交通大学信息科学与技术学院	6	31	4.0	5.0
2	刘晓庆	西南交通大学信息科学与技术学院	6	23	3.0	4.0