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

Abstract

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\le 3$. This paper makes a significant progress by presenting a $(2k-1){\alpha }_0$ approximation algorithm for general $k$ and $m$ with $m\ge k$, where ${\alpha }_0$ is the performance ratio for the minimum CDS problem. Using currently best known ratio for ${\alpha }_0$, our algorithm has performance ratio $O(\ln \Delta )$, where $\Delta$ is the maximum degree of the graph.

Cited by in corpus (1)

• On combinatorial optimization for dominating sets (literature survey, new models)