You are here

Binary Merge Model Representation of the Graph Colouring Problem

TitleBinary Merge Model Representation of the Graph Colouring Problem
Publication TypeConference Paper
Year of Publication2004
AuthorsJuhos, I, Tóth, A, van Hemert, JI
Conference NameSpringer Lecture Notes on Computer Science
PublisherSpringer-Verlag, Berlin
EditorGottlieb, J, Raidl, G
ISBN Number3-540-21367-8
Keywordsconstraint satisfaction; graph colouring
Abstract

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.

Full Text