Approximation Algorithm for Minimum Weight $(k,m)$-CDS Problem in Unit Disk Graph

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\ge k$. Prior to this work, constant approximation algorithms are known for $k=1$ with weight and $2\le k\le 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 +2.5k\rho )$ for $k\ge 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.)

Cited by in corpus (2)

• Approximation Algorithm for Fault-Tolerant Virtual Backbone in Wireless Sensor Networks
• Neural optimization for quantum architectures: graph embedding problems with Distance Encoder Networks