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

• 作者: 刘晓庆 李玉华
• 来源期刊: 电脑知识与技术：学术交流
• 学科: 工学
• 关键词: 连通支配集 独立集 集中式算法 有序表
• 年，卷（期）: 2009,（4）
• 页码范围: 2634-2635
• 页数: 2页
• 分类号: TP301.6

摘要

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

作者信息

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