Connected dominating set

1. $V\text{'}$ is a dominating set of G, and
2. the subgraph induced by $V\text{'}$ is connected.

Connected dominating set 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.

See also

• Dominating set problem