Parallel genetic algorithm for minimum dominating set problem
Cu Nguyen Giap, Dinh Thi Ha · 2014
In this paper, we study parallel genetic algorithm for solving a well-known NP-hard problem in graph theory that is minimum dominating set problem. We have, at first, investigated for a high performance parallel genetic algorithm for such problem. The experiment proves that the single distributed population parallel genetic algorithm is a desired solution. Secondly, we have investigated how difficult it is to find the suitable formulations of the genetic operations for our parallel genetic algorithm. Finally, we run the proposed algorithm on variant data sets, which are designed specifically for minimum dominating set problem, to navigate the best parameter for each genetic operation.