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 $V'\subset V$ such that

$\ V'$ is a dominating set of G, and
the subgraph induced by $\ V'$ 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.