01085nas a2200193 4500008004100000245007900041210006900120260002800189300001300217520050300230653002800733653002000761100001300781700001300794700001600807700001300823700001600836856003900852 2005 eng d00aHeuristic Colour Assignment Strategies for Merge Models in Graph Colouring0 aHeuristic Colour Assignment Strategies for Merge Models in Graph bSpringer-Verlag, Berlin a132--1433 aIn 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.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aTóth, A1 aHemert, J I1 aRaidl, G1 aGottlieb, J uhttp://research.nesc.ac.uk/node/1701019nas a2200205 4500008004100000020001800041245006900059210006900128260002800197300001300225520041700238653002800655653002000683100001300703700001300716700001600729700001600745700001300761856003900774 2004 eng d a3-540-21367-800aBinary Merge Model Representation of the Graph Colouring Problem0 aBinary Merge Model Representation of the Graph Colouring Problem bSpringer-Verlag, Berlin a124--1343 aThis 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.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aTóth, A1 aHemert, J I1 aGottlieb, J1 aRaidl, G uhttp://research.nesc.ac.uk/node/2100990nas a2200181 4500008004100000245006900041210006600110300001300176520046400189653002800653653002000681100001300701700001300714700001400727700001200741700001600753856003900769 2003 eng d00aA new permutation model for solving the graph k-coloring problem0 anew permutation model for solving the graph kcoloring problem a189--1993 aThis 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.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aTóth, A1 aTezuka, M1 aTann, P1 aHemert, J I uhttp://research.nesc.ac.uk/node/24