Article (Published version) (176 Kb)  Private access
Highlights
More informations
Title 
An adaptive memory algorithm for the kcoloring problem 

Authors  
Published in  Discrete Applied Mathematics. 2008, vol. 156, p. 267279  
Abstract  Let G = (V ,E) be a graph with vertex set V and edge set E. The kcoloring 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 kcoloring 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 heuristics — Adaptive memory algorithms — Tabu search — Graph coloring  
Full text  
Structures  
Citation (ISO format)  GALINIER, Philippe, HERTZ, Alain, ZUFFEREY, Nicolas. An adaptive memory algorithm for the kcoloring problem. In: Discrete Applied Mathematics, 2008, vol. 156, p. 267279. https://archiveouverte.unige.ch/unige:26172 