Two Meta-heuristics for the Minimum Connected Dominating Set Problem with an Application in Wireless Networks

In this paper, we proposed two methods to solve Minimum Connected Dominating Set (MCDS) problem. It is known that efficient methods for computing the MCDS are essential for solving many practical problems, such as finding a minimum size backbone in ad hoc networks. We propose two methods to solve the MCDS problem. In the first method, we propose a new hybrid method based on genetic Algorithm combine with local search strategy for the MCDS problem called Memetic Algorithm for the MCDS problem (MA-MCDS). MAMCDS uses local search and intensification schemes beside the GA search methodology in order to achieve faster performance. The scorned method is called Simulated Annealing for the MCDS problem (SA-MCDS). SA-MCDS is invoked to enhance the stochastic local search (SLS) method with the ability of escaping from local solutions. In addition, proposed methods invoke a new objective function to effectively measure the solution qualities. The proposed algorithms is tested on a number of publically available benchmark test graph sets and numerical results indicate that they are working well in terms of solution qualities and computational costs.