您的位置:首页  > 论文页面

圆盘图中最小连通k-全控制集问题的算法

发表时间:2010-01-15  浏览量:1702  下载量:730
全部作者: 李业芳,艾文宝,帅天平
作者单位: 北京邮电大学理学院
摘 要: 在无线传感器网络(wireless sensor network,WSN)中,为更好地构造虚拟骨干网作为路由协议以减少广播风暴,针对不同传输半径,对通过连通控制集构造的虚拟骨干网进行研究,并提出双向圆盘图中的最小连通k-全控制集(minimum connected k-tuple totally dominating set, k-MTCDS)问题,给出了一个集中式近似算法来构造k-MTCDS,通过理论分析,该算法具有较好的近似比。
关 键 词: 组合最优化;最小连通k-全控制集;极大独立集;双向圆盘图;无线传感器网络
Title: Algorithm for minimum connected k-tuple totally dominating set problem in disk graph
Author: LI Yefang, AI Wenbao, SHUAI Tianping
Organization: School of Science, Beijing University of Posts and Telecommunications
Abstract: To alleviate the broadcasting storm in wireless sensor network (WSN), fault tolerant connected dominating set (CDS) whose nodes have different transmission ranges was studied as the virtual backbone in this paper. A general fault tolerant CDS problem, called k-MTCDS (minimum connected k-tuple totally dominating set), was proposed in bidirectional disk graph and a centralized approximation algorithm which has a better approximation ratio was given.
Key words: combinatorial optimization; minimum connected k-tuple totally dominating set; maximum independent set; bidirectional disk graph; wireless senor network
发表期数: 2010年1月第1期
引用格式: 李业芳,艾文宝,帅天平. 圆盘图中最小连通k-全控制集问题的算法[J]. 中国科技论文在线精品论文,2010,3(1):70-73.
 
0 评论数 0
暂无评论
友情链接