00602nas a2200181 4500008004100000245010900041210006900150260001300219300001300232653002800245653002900273653002000302100001300322700001600335700001300351700001600364856004000380 2008 eng d00aContraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem0 aContractionBased Heuristics to Improve the Efficiency of Algorit bSpringer a167--18410aconstraint satisfaction10aevolutionary computation10agraph colouring1 aJuhos, I1 aHemert, J I1 aCotta, C1 aHemert, J I uhttp://research.nesc.ac.uk/node/32201306nas a2200193 4500008004100000245007100041210006900112260001300181300001200194490000900206520073400215653002900949653002000978100002200998700001701020700001701037700001801054856004001072 2008 eng d00aGraph Colouring Heuristics Guided by Higher Order Graph Properties0 aGraph Colouring Heuristics Guided by Higher Order Graph Properti bSpringer a97--1090 v49723 aGraph 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.10aevolutionary computation10agraph colouring1 aJuhos, Istv\'{a}n1 aHemert, Jano1 aHemert, Jano1 aCotta, Carlos uhttp://research.nesc.ac.uk/node/23301191nas a2200181 4500008004100000245008500041210006900126260002000195300001300215520063600228653002800864653002000892100001300912700001600925700001600941700001300957856003900970 2006 eng d00aImproving Graph Colouring Algorithms and Heuristics Using a Novel Representation0 aImproving Graph Colouring Algorithms and Heuristics Using a Nove bSpringer-Verlag a123--1343 aWe introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of an algorithm. Moreover, our model provides useful information for guiding heuristics as well as a compact description for algorithms. To verify the potential of the model, we use it in dsatur, in an evolutionary algorithm, and in the same evolutionary algorithm extended with heuristics. An empiricial investigation is performed to show an increase in efficiency on two problem suites , a set of practical problem instances and a set of hard problem instances from the phase transition.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aHemert, J I1 aGottlieb, J1 aRaidl, G uhttp://research.nesc.ac.uk/node/1101421nas a2200145 4500008004100000245010900041210006900150300001100219490000600230520095200236653002001188100001301208700001601221856003801237 2006 eng d00aIncreasing the efficiency of graph colouring algorithms with a representation based on vector operations0 aIncreasing the efficiency of graph colouring algorithms with a r a24--330 v13 aWe introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of graph colouring algorithms. Moreover, this model provides useful information to aid in the creation of heuristics that can make the colouring process even faster. It also serves as a compact definition for the description of graph colouring algorithms. To verify the potential of the model, we use it in the complete algorithm DSATUR, and in two version of an incomplete approximation algorithm; an evolutionary algorithm and the same evolutionary algorithm extended with guiding heuristics. Both theoretical and empirical results are provided investigation is performed to show an increase in the efficiency of solving graph colouring problems. Two problem suites were used for the empirical evidence: a set of practical problem instances and a set of hard problem instances from the phase transition.10agraph colouring1 aJuhos, I1 aHemert, J I uhttp://research.nesc.ac.uk/node/701085nas 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/2401452nas a2200181 4500008004100000245005700041210005700098260003100155300001100186490000600197520093500203653002801138653002001166100001501186700001401201700001601215856003901231 1998 eng d00aGraph Coloring with Adaptive Evolutionary Algorithms0 aGraph Coloring with Adaptive Evolutionary Algorithms bKluwer Academic Publishers a25--460 v43 aThis paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EA). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping GA on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping GA and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.10aconstraint satisfaction10agraph colouring1 aEiben, A E1 aHauw, J K1 aHemert, J I uhttp://research.nesc.ac.uk/node/47