Details

Autor(en) / Beteiligte

• Shi, Yishuo
• Zhang, Zhao
• Mo, Yuchang
• Du, Ding-Zhu

Titel

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

Ist Teil von

• IEEE/ACM transactions on networking, 2017-04, Vol.25 (2), p.925-933

Ort / Verlag

New York: IEEE

Erscheinungsjahr

2017

Quelle

IEEE Electronic Library (IEL)

Beschreibungen/Notizen

• 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).