Connected dominating set
From Wikipedia, the free encyclopedia
In graph theory, a connected dominating set of a graph G = (V,E) is a set of vertices 
such that
is a dominating set of G, and- the subgraph induced by is connected.
Connected dominating sets are useful in the computation of routing for mobile ad-hoc networks and other network problems. However, the computation of the minimum connected dominating set over a given graph is in general an NP-complete problem, so approximations must be employed in practice.
