by Juhos, I and van Hemert, J
Abstract:
Graph vertex colouring can be defined in such a way where colour assignments are substituted by vertex contractions. We present various hyper-graph representations for the graph colouring problem all based on the approach where vertices are merged into groups. In this paper, we show this provides a uniform and compact way to define algorithms, both of a complete or a heuristic nature. Moreover, the representation provides information useful to guide algorithms during their search. In this paper we focus on the quality of solutions obtained by graph colouring heuristics that make use of higher order properties derived during the search. An evolutionary algorithm is used to search permutations of possible merge orderings.
Reference:
Graph Colouring Heuristics Guided by Higher Order Graph Properties (Juhos, I and van Hemert, J), In Evol Comput in Comb Optim (van Hemert, J, Cotta, C, eds.), Springer, volume 4972, 2008.
Bibtex Entry:
@article{JH2008,
_day = {26},
abstract = {Graph vertex colouring can be defined in such a way where colour assignments are substituted by vertex contractions. We present various hyper-graph representations for the graph colouring problem all based on the approach where vertices are merged into groups. In this paper, we show this provides a uniform and compact way to define algorithms, both of a complete or a heuristic nature. Moreover, the representation provides information useful to guide algorithms during their search. In this paper we focus on the quality of solutions obtained by graph colouring heuristics that make use of higher order properties derived during the search. An evolutionary algorithm is used to search permutations of possible merge orderings.},
author = {Juhos, I and van Hemert, J},
date-added = {2008-08-18 12:44:11 +0100},
date-modified = {2011-06-06 19:47:32 +0100},
editor = {van Hemert, J and Cotta, C},
journal = {Evol Comput in Comb Optim},
keywords = {graph colouring; evolutionary computation; constraint satisfaction},
notedisabled = {\textsc{One of three papers nominated for the Best Paper Award for 2008.}},
pages = {97--108},
publisher = {Springer},
series = {{LNCS}},
title = {Graph Colouring Heuristics Guided by Higher Order Graph Properties},
volume = {4972},
year = {2008}}