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

An adaptive memory algorithm for the k-coloring problem

Authors
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) - private document Private access
Structures
Citation
(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

170 hits

0 download

Update

Deposited on : 2013-02-04

Export document
Format :
Citation style :