Solving Connected Dominating Set Problem in Unit Disk Graphs by Genetic Algorithms

In this paper, the authors use Genetic Algorithms to find the Minimum Connected Dominating Set (MCDS) of Unit Disk Graphs (UDG). UDGs are used for modeling ad-hoc networks and finding MCDS in such graphs is a promising approach to construct an efficient virtual backbone in wireless ad-hoc networks. The MCDS problem is proved to be NP-complete. The simulation results show that the proposed algorithm outperforms the existing CDS-based backbone formation algorithms in terms of the backbone size.