一种高效的最小连通支配集贪心算法

• 作者: 王占华 赵学锋 高红玉
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 最小连通支配集 单位圆盘图 贪心算法 广度优先搜索
• 年，卷（期）: 2012,（13）
• 所属期刊栏目: 网络、通信、安全
• 页码范围: 89-93
• 分类号: TP393
• 字数: 4180字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2012.13.020

摘要

连通支配集(CDS)在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点.提出了一个同时处理多个节点的贪心算法( GCDS),依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点；最终所有支配点构成一个近似最小连通支配集.在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵学锋	西北师范大学数学与信息科学学院	24	60	4.0	6.0
2	高红玉	西北师范大学数学与信息科学学院	3	12	2.0	3.0
3	王占华	西北师范大学数学与信息科学学院	2	9	2.0	2.0