You are here

Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring

TitleHeuristic Colour Assignment Strategies for Merge Models in Graph Colouring
Publication TypeConference Paper
Year of Publication2005
AuthorsJuhos, I, Tóth, A, van Hemert, JI
Conference NameSpringer Lecture Notes on Computer Science
PublisherSpringer-Verlag, Berlin
EditorRaidl, G, Gottlieb, J
Keywordsconstraint satisfaction; graph colouring
Abstract

In this paper, we combine a powerful representation for graph colouring problems with different heuristic strategies for colour assignment. Our novel strategies employ heuristics that exploit information about the partial colouring in an aim to improve performance. An evolutionary algorithm is used to drive the search. We compare the different strategies to each other on several very hard benchmarks and on generated problem instances, and show where the novel strategies improve the efficiency.

Full Text