by I Juhos, A Tóth and van Hemert, J
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.
Reference:
Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring (I Juhos, A Tóth and van Hemert, J), In Evol Comput in Comb Optim (G Raidl, J Gottlieb, eds.), Springer, volume 3448, 2005.
Bibtex Entry:
@article{JTH2005,
_day = {30},
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.},
author = {I Juhos and A T{\'o}th and van Hemert, J},
booktitle = {Evol Comput in Comb Optim},
date-added = {2008-08-18 12:44:11 +0100},
date-modified = {2009-09-30 14:03:58 +0100},
editor = {G Raidl and J Gottlieb},
journal = {Evol Comput in Comb Optim},
keywords = {constraint satisfaction; graph colouring},
pages = {132--143},
pdf = {http://www.vanhemert.co.uk/publications/evocop2005.Heuristics_Colour_Assignment_Strategies_for_Merge_Models_in_Graph_Colouring.pdf},
publisher = {Springer},
series = {{LNCS}},
title = {Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring},
volume = {3448},
year = {2005}}