TY - CONF
T1 - Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring
T2 - Springer Lecture Notes on Computer Science
Y1 - 2005
A1 - Juhos, I.
A1 - Tóth, A.
A1 - van Hemert, J. I.
ED - G. Raidl
ED - J. Gottlieb
KW - constraint satisfaction
KW - graph colouring
AB - 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.
JF - Springer Lecture Notes on Computer Science
PB - Springer-Verlag, Berlin
ER -
TY - CONF
T1 - Binary Merge Model Representation of the Graph Colouring Problem
T2 - Springer Lecture Notes on Computer Science
Y1 - 2004
A1 - Juhos, I.
A1 - Tóth, A.
A1 - van Hemert, J. I.
ED - J. Gottlieb
ED - G. Raidl
KW - constraint satisfaction
KW - graph colouring
AB - This paper describes a novel representation and ordering model that aided by an evolutionary algorithm, is used in solving the graph \emph{k}-colouring problem. Its strength lies in reducing the search space by breaking symmetry. An empirical comparison is made with two other algorithms on a standard suit of problem instances and on a suit of instances in the phase transition where it shows promising results.
JF - Springer Lecture Notes on Computer Science
PB - Springer-Verlag, Berlin
SN - 3-540-21367-8
ER -
TY - CONF
T1 - A new permutation model for solving the graph k-coloring problem
T2 - Kalmàr Workshop on Logic and Computer Science
Y1 - 2003
A1 - Juhos, I.
A1 - Tóth, A.
A1 - Tezuka, M.
A1 - Tann, P.
A1 - van Hemert, J. I.
KW - constraint satisfaction
KW - graph colouring
AB - This paper describes a novel representation and ordering model, that is aided by an evolutionary algorithm, is used in solving the graph k-coloring. A comparison is made between the new representation and an improved version of the traditional graph coloring technique DSATUR on an extensive list of graph k-coloring problem instances with different properties. The results show that our model outperforms the improved DSATUR on most of the problem instances.
JF - Kalmàr Workshop on Logic and Computer Science
ER -