Events

A connected dominating set (CDS) for a graph G = (V, E) is a subset V´ of V such that each node in V – V´ is adjacent to some node in V´, and V´ is a connected subgraph.

CDS discovering algorithms have proved to be very useful in finding the optimal virtual backbone for routing in wireless ad hoc networks. However, it is NP-hard to find a minimum connected dominating set (MCDS).