Efficient Graph Coloring with Parallel Genetic Algorithms

Zbigniew Kokosiński

Faculty of Electrical and Computer Engineering
Cracow University of Technology
ul. Warszawska 24
31-155 Kraków, Poland
Krzysztof Kwarciany

Faculty of Electrical and Computer Engineering
Cracow University of Technology
ul. Warszawska 24
31-155 Kraków, Poland
Marcin Kołodziej

Faculty of Electrical and Computer Engineering
Cracow University of Technology
ul. Warszawska 24
31-155 Kraków, Poland

Efficient Graph Coloring with Parallel Genetic Algorithms

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

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.

reference: Vol. 24, 2005, No. 2, pp. 123–147

Computing and Informatics

formerly Computers and Artificial Intelligence

Efficient Graph Coloring with Parallel Genetic Algorithms