Paper detail

Performance Guaranteed Approximation Algorithm for Minimum $k$-Connected $m$-Fold Dominating Set

To achieve an efficient routing in a wireless sensor network, connected dominating set (CDS) is used as virtual backbone. A fault-tolerant virtual backbone can be modeled as a $(k,m)$-CDS. For a connected graph $G=(V,E)$ and two fixed integers $k$ and $m$, a node set $C\subseteq V$ is a $(k,m)$-CDS of $G$ if every node in $V\setminus C$ has at least $m$ neighbors in $C$, and the subgraph of $G$ induced by $C$ is $k$-connected. Previous to this work, approximation algorithms with guaranteed performance ratio in a general graph were know only for $k\leq 3$. This paper makes a significant progress by presenting a $(2k-1)α_0$ approximation algorithm for general $k$ and $m$ with $m\geq k$, where $α_0$ is the performance ratio for the minimum CDS problem. Using currently best known ratio for $α_0$, our algorithm has performance ratio $O(\lnΔ)$, where $Δ$ is the maximum degree of the graph.