  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)\alpha_0$ approximation algorithm for general $k$ and $m$
with $m\geq 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.
