Solving Connected Dominating Set Problem in Unit Disk Graphs by Genetic Algorithms
Source: Islamic Azad University
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.