构建最小k重控制集的概率算法  

Probabilistic algorithm for minimum k-fold dominating set problem

作　　者：马文凯[1] 李德英[1] 张昭[2] 

机构地区：[1]中国人民大学信息学院,北京100872 [2]新疆大学数学学院,乌鲁木齐830046

出　　处：《中国科学：数学》2011年第8期725-732,共8页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:61070191);国家自然科学基金(批准号:10971255);中国人民大学科学研究基金(中央高校基本科研业务费专项资金)(批准号:10XNJ032)资助项目;国家教育部科学技术重点项目(批准号:208161);新世纪优秀人才支持计划和高等学校骨干教师资助计划支持

摘　　要：点集D V(G)称为图G的k重控制集,如果D满足V(G)-D中任意结点在D中至少有k个邻居.在无线网络中,最小k重控制集(MkDS)用以构建健壮的虚拟骨干网.构建虚拟骨干网是无线网络中最基本也是最重要的问题.在本文中,我们提出一种快速的分布式概率算法来构建k重控制集.我们构建的k重控制集的期望大小不超过最优解的O(k2)倍.算法的运行时间复杂度为O((△log△+loglogn)n),其中△=max{|D(p)|},D(p)是以p为中心半径为1的圆盘中的结点,最大值的比较范围是给定集合中所有的p点.A k-fold dominating set of a graph G is a node subset D of V （G） such that every node in V （G）-D has at least k neighbors in D. Minimum k-fold dominating sets （MkDS） are utilized to build robust virtual backbones in wireless networks. In this paper, we propose a fast distributed probabilistic algorithm to construct an MkDS.The expected size of the k-dominating set which we construct is no more than O（k2） times of the optimal, and the time complexity is O（（△ log △ ＋ log log n）n）, where △ = max ｜D（p）｜, D（p） is the set of nodes falling into the disk with center p and radius 1, and the maximum is taken over all p in the given set.

关 键 词：k重控制集 概率算法 近似算法 单位圆盘图 

分 类 号：O157.5[理学—数学]