构建最小k重控制集的概率算法
外文标题：Probabilistic algorithm for minimum k-fold dominating set problem
文献类型：期刊
作者：马文凯[1]
机构： 中国人民大学信息学院, 北京 100872, 中国; 新疆大学数学学院, 乌鲁木齐, 新疆 830046, 中国
年：2011
期刊名称：中国科学. 数学
卷：41
期：8
页码范围：725-732
增刊：增刊
收录情况：CSCD(CSCD:4268293)
所属部门：信息学院
语言：中文
ISSN：1674-7216
人气指数：1
浏览次数：1
基金：国家自然科学基金; 国家自然科学基金; 中国人民大学科学研究基金中央高校基本科研业务费专项资金; 国家教育部科学技术重点项目; 新世纪优秀人才支持计划和高等学校骨干教师资助计划支持
关键词：k重控制集; 概率算法; 近似算法; 单位圆盘图
摘要：点集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点.
作者其他论文
无线传感器网络位置隐私保护技术.彭辉;陈红;张晓莹,等.软件学报.2015,26(3),617-639.
一种无线传感器网络中连续的Top-k区域查询方法..0.
无线传感器网络能量高效综述.李德英;陈文萍;霍瑞龙,等.计算机科学.2008,35(11),8-12,35.
无线自组织网络中能量有效的广播与组播.李政;李德英.软件学报.2010,21(8),2023-2036.
视频传感器网络覆盖问题.陈文萍;杨萌;洪弋,等.计算机应用.2013,33(6),1489-1494,1522.
