en
Proceedings chapter
English

Adaptive Memory Algorithms for Graph Coloring

Presented at Ithaca (USA)
Publication date2002
Abstract

Let G=(V,E) be a graph with vertex set V and edge set E. The graph coloring problem consists in assigning an integer (called color) to each vertex so that adjacent vertices get different colors, and the total number of different colors is minimized. The adaptive memory algorithm is an hybrid evolutionary heuristic based on a central memory. At each generation, the idea is to use the information of a central memory for producing an offspring which is then improved by using a local search algorithm. The so obtained solution is finally used to update the information contained in the memory. In this paper, we propose an adaptive memory algorithm to the graph coloring problem. The results obtained so far give evidence that our method is competitive with the best known coloring algorithms.

eng
Citation (ISO format)
GALINIER, Philippe, HERTZ, Alain, ZUFFEREY, Nicolas. Adaptive Memory Algorithms for Graph Coloring. In: Proceedings of the Computational Symposium on Graph Coloring and its Generalizations. Ithaca (USA). [s.l.] : [s.n.], 2002.
Identifiers
  • PID : unige:26179
475views
0downloads

Technical informations

Creation01/29/2013 1:28:00 PM
First validation01/29/2013 1:28:00 PM
Update time02/09/2024 12:51:10 PM
Status update02/09/2024 12:51:10 PM
Last indexation02/09/2024 12:51:12 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack