UNIGE document Scientific Article
previous document  unige:26172  next document
add to browser collection

An adaptive memory algorithm for the k-coloring problem

Galinier, Philippe
Hertz, Alain
Published in Discrete Applied Mathematics. 2008, vol. 156, p. 267-279
Abstract Let G = (V ,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1, ..., k}) to each vertex of G so that no edge has both endpoints with the same color. 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-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.
Keywords Hybrid evolutionary heuristicsAdaptive memory algorithmsTabu searchGraph coloring
Full text
Article (Published version) (176 Kb) - document accessible for UNIGE members only Limited access to UNIGE
(ISO format)
GALINIER, Philippe, HERTZ, Alain, ZUFFEREY, Nicolas. An adaptive memory algorithm for the k-coloring problem. In: Discrete Applied Mathematics, 2008, vol. 156, p. 267-279. https://archive-ouverte.unige.ch/unige:26172

364 hits

0 download


Deposited on : 2013-02-04

Export document
Format :
Citation style :