求解最小连通r-跳k-支配集的启发式算法

• 作者: 赵学锋
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 最小连通r-跳k-支配集 启发式算法 单位圆盘图 堆 广度优先搜索 节点度
• 年，卷（期）: 2012,（21）
• 所属期刊栏目: 网络与通信
• 页码范围: 67-69,73
• 页数: 4页
• 分类号: TP393
• 字数: 3538字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2012.21.018

摘要

针对最小连通r-跳k-支配集的求解问题,提出一种基于节点度贪心策略的启发式算法.把网络节点集合作为初始解,从中选出度数最小的节点,通过判断节点的连通性决定是否将该节点从当前可行解中删除,由此逐步缩小连通支配集的规模,直至处理完所有节点.在单位圆盘图上进行算法复杂性分析和模拟实验,结果表明,相比同类算法,该算法得到的连通r-跳k-支配点集更少,且性能稳定.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵学锋	西北师范大学数学与信息科学学院	24	60	4.0	6.0