Message-optimal connected dominating sets in mobile ad hoc networks

A connected dominating set (CDS) for a graph G(V,E) is a subset V1 of V, such that each node in V--V1 is adjacent to some node in V1, and V1 induces a connected subgraph. A CDS has been proposed as a virtual backbone for routing in wireless ad hoc networks. However, it is NP-hard to find a minimum connected dominating set (MCDS). Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a very...