Serving as a virtual backbone for wireless ad hoc networks, the connected
dominating set problem has been widely studied. We design a robust and
survivable connected dominating set for a virtual backbone of a larger graph for
ad hoc network. More specifically, we study the (k; l)-connected d-dominating
set problem. Given a graph G = (V;E), a subset D V is a (k; l)-connected ddominating
set if the subgraph induced by D has mixed connectivity at least (k; l)
and every vertex outside of S has at least d neighbors from D. The type of virtual
backbone is survivable and also robust for sending message under certain number
of both node and link failures.We study the properties of such dominating set and
also IP formulations. In addition, we design a cutting plane algorithm to solve it.
| 