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.