两跳支配集的高效近似算法

• 作者: 王占华 赵学锋 高红玉
• 来源期刊: 西北师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 2 hop-支配集 贪心算法 单位圆盘图
• 年，卷（期）: 2011,（5）
• 所属期刊栏目: 计算机与信息科学
• 页码范围: 46-49
• 分类号: TP301.6
• 字数: 3005字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-988X.2011.05.010

摘要

提出一种求解连通图2-hop支配集(2-DS)的贪心算法.首先将图中每个节点和其两跳邻居节点连接,然后在此基础上求图的2-hop支配集,最后采用修剪规则剔除支配集中的冗余节点.由于支配点支配2-hop内的邻居节点,从而构造出较小的支配集.仿真结果表明,新算法优于其他已有算法.

作者信息

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