On minimum m -connected k -dominating set problem in unit disc graphs

详细信息    查看全文

• 作者：Weiping Shang ; Frances Yao ; Pengjun Wan and Xiaodong Hu
• 关键词：k ; dominating set ; m ; connectivity ; Unit disc graph ; Approximation algorithm ; Wireless sensor networks
• 刊名：Journal of Combinatorial Optimization
• 出版年：2008
• 出版时间：August, 2008
• 年：2008
• 卷：16
• 期：2
• 页码：99-106
• 全文大小：251.2 KB

文摘

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m.