You are here

A new permutation model for solving the graph k-coloring problem

TitleA new permutation model for solving the graph k-coloring problem
Publication TypeConference Paper
Year of Publication2003
AuthorsJuhos, I, Tóth, A, Tezuka, M, Tann, P, van Hemert, JI
Conference NameKalmàr Workshop on Logic and Computer Science
Keywordsconstraint satisfaction; graph colouring
Abstract

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.

Full Text