Approximation Algorithm for Minimum Weight Fault-Tolerant Virtual Backbone in Unit Disk Graphs

摘要

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 (α+5ρ) for k≥3 and (α+2.5ρ) for k=2 , where α 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).