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

Efficient approximation algorithm for two-hop dominating set

作　　者：赵学锋[1] 王占华[1] 高红玉[1] 

机构地区：[1]西北师范大学数学与信息科学学院,甘肃兰州730070

出　　处：《西北师范大学学报（自然科学版）》2011年第5期46-49,共4页Journal of Northwest Normal University(Natural Science)

基　　金：甘肃省科技攻关项目(2GS035-A052-011)

摘　　要：提出一种求解连通图2-hop支配集(2-DS)的贪心算法.首先将图中每个节点和其两跳邻居节点连接,然后在此基础上求图的2-hop支配集,最后采用修剪规则剔除支配集中的冗余节点.由于支配点支配2-hop内的邻居节点,从而构造出较小的支配集.仿真结果表明,新算法优于其他已有算法.This paper proposes a greedy algorithm to solve two hop dominating set（DS）problem in connected graphs.Firstly,each node of graph is connected with its two-hop neighbor nodes.And then two-hop dominating sets of this graph are found.Lastly,redundant nodes of the dominating set are removed using prune rules.The dominating node dominates adjacent nodes within its two-hop so as to construct smaller dominating set.Theoretical analysis and simulation results show that presented algorithm is superior to other existing approaches.

关 键 词：2hop-支配集 贪心算法 单位圆盘图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]