Paper Info
Title
Approximation Algorithm for Minimum Weight Fault-Tolerant Virtual Backbone in Unit Disk Graphs
Abstract
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\geq k$ . Prior to this paper, constant approximation algorithms are known for $k=1$ with weight and $2\leq k\leq 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\geq 3$ and $(\alpha +2.5\rho )$ for $k=2$ , where $\alpha $ is the performance ratio for the minimum weight $m$ -fold dominating set problem and $\rho $ is the performance ratio for the subset $k$ -connected subgraph problem (both problems are known to have constant performance ratios).
Year
DOI
Venue
2017
10.1109/TNET.2016.2607723
IEEE/ACM Transactions on Networking (TON)
Keywords
DocType
Volume
Approximation algorithms,Sensors,Algorithm design and analysis,Wireless sensor networks,Fault tolerance,Fault tolerant systems,Joining processes
Journal
25
Issue
ISSN
Citations 
2
1063-6692
2
PageRank 
References 
Authors
0.37
0
4
Name
Order
Citations
PageRank
Yishuo Shi1223.23
Zhao Zhang2706102.46
Yuchang Mo320.70
D.-Z. Du421952.53