Back

G-2003-35

An Adaptive Memory Algorithm for the k-Colouring Problem

, , and

BibTeX reference

Let G=(V,E) be a graph with vertex set V and edge set E. The k-colouring problem is to assign a colour (a number chosen in {1,...,k}) to each vertex of G so that no edge has both endpoints with the same colour. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-colouring problem. Computational experiments give evidence that this new algorithm is competitive with and simpler and more flexible than the best known graph colouring algorithms.

, 20 pages

This cahier was revised in April 2004

Research Axis

Publication

An adaptive memory algorithm for the k-colouring problem
, , and
Discrete Applied Mathematics, 156, 267–279, 2008 BibTeX reference