您的位置：首页 > 论文页面
圆盘图中最小连通k-全控制集问题的算法
发表时间：2010-01-15 浏览量：2308 下载量：989
| 全部作者： | 李业芳，艾文宝，帅天平 |
| 作者单位： | 北京邮电大学理学院 |
| 摘 要： | 在无线传感器网络（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. |
1
评论数 0请您登录
暂无评论
下载全文
多维论文