Efficient Graph Coloring with Parallel Genetic Algorithms

Authors

  • Zbigniew Kokosiński
  • Krzysztof Kwarciany
  • Marcin Kołodziej

Keywords:

Graph coloring, parallel genetic algorithm, migration model, CEX crossover, SPPX crossover

Abstract

In this paper a new parallel genetic algorithm for coloring graph vertices is presented. In the algorithm we apply a migration model of parallelism and define two new recombination operators SPPX and CEX. For comparison two problem-oriented crossover operators UISX and GPX are selected. The performance of the algorithm is verified by computer experiments on a set of standard graph coloring instances.

Downloads

Download data is not yet available.

Downloads

Published

2012-02-03

How to Cite

Kokosiński, Z., Kwarciany, K., & Kołodziej, M. (2012). Efficient Graph Coloring with Parallel Genetic Algorithms. COMPUTING AND INFORMATICS, 24(2), 123–147. Retrieved from http://www.cai.sk/ojs/index.php/cai/article/view/371