.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithm for Minimum Weight Fault-Tolerant Virtual Backbone in Unit Disk Graphs
.png){kind=icon}
OA
AI
DOI：10.1109/TNET.2016.2607723.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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).
Keywords:
Wireless sensor network
fault tolerant
connected dominating set
approximation algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K
View more organizations