e-Science logo Nesc logo
 
 
About NeSC
e-Science Institute
e-Science Hub
TOE
Contacts
e-Science Events
Resources
Newsroom
Presentations & Lectures
Technical Papers
Global Grid Links
Projects
UK e-Science Centres
UK e-Science Teams
Career Opportunities
Bibliographic Database
 

 

Paper ID: 2703

A new permutation model for solving the graph k-coloring problem
Juhos,I. Tóth,A. Tezuka,M. Tann,P. van Hemert,J.I. ,

Appeared in: Kalmàr Workshop on Logic and Computer Science,
Page Numbers:189--199
Publisher:
Year: 2003
ISBN/ISSN:
Contributing Organisation(s):
Field of Science: e-Science

URL:

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.

Keywords: constraint satisfaction, graph colouring,


BIB DOC HTM HTML PDF PPT PS RTF TEX TXT ZIP




 

Last Updated: 22 Jun 12 11:02
This is an archived website, preserved and hosted by the School of Physics and Astronomy at the University of Edinburgh. The School of Physics and Astronomy takes no responsibility for the content, accuracy or freshness of this website. Please email webmaster [at] ph [dot] ed [dot] ac [dot] uk for enquiries about this archive.