Title :
Parallel genetic algorithm for minimum dominating set problem
Author :
Cu Nguyen Giap ; Dinh Thi Ha
Author_Institution :
Inf. Syst. for Econ., Vietnam Univ. of Commerce, Hanoi, Vietnam
Abstract :
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.
Keywords :
computational complexity; genetic algorithms; graph theory; parallel algorithms; set theory; NP-hard problem; genetic operation; graph theory; high performance parallel genetic algorithm; minimum dominating set problem; single distributed population parallel genetic algorithm; variant data set; Algorithm design and analysis; Biological cells; Electronics packaging; Generators; Genetic algorithms; Sociology; Statistics; data generator; dominating set; genetic algorithm; minimum; parallel;
Conference_Titel :
Computing, Management and Telecommunications (ComManTel), 2014 International Conference on
Conference_Location :
Da Nang
Print_ISBN :
978-1-4799-2904-7
DOI :
10.1109/ComManTel.2014.6825598
