科研之友
微信
新浪微博
Facebook
分享链接
摘要
In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight (k, m)-CDS problem in unit disk graphs under the assumption that k and m are two fixed constants with m >= k. Prior to this paper, constant approximation algorithms are known for k = 1 with weight and 2 <= k <= 3 without weight. Our result is the first constant approximation algorithm for the (k, m)-CDS problem with general k, m and with weight. The performance ratio is (alpha+5 rho) for k >= 3 and (alpha+2.5 rho) for k = 2, where a is the performance ratio for the minimum weight m-fold dominating set problem and. is the performance ratio for the subset k-connected subgraph problem (both problems are known to have constant performance ratios).
