2015/08/31 by Yishuo Shi, Zhao Zhang, Ding-Zhu Du +1 · 38 citations
Computer Science · #Approximation algorithm #Complexity and Algorithms in Graphs #Connected dominating set #Constant (computer programming) #Dominating set #Energy Efficient Wireless Sensor Networks #Minimum weight #Mobile Ad Hoc Networks #Set (abstract data type) #Unit disk graph #cs.DM #cs.DS
paper · pdf · doi:10.1109/tnet.2016.2607723
published in IEEE/ACM Transactions on Networking 25(2), 925-933 (Institute of Electrical and Electronics Engineers)
openalex created_date 2016/06/24 · openalex publication_date 2016/09/28 · arxiv created 2019/01/04 · arxiv updated 2019/01/07 · openalex updated_date 2026/08/05
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ρ) fork ≥ 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).