Cookie Control

This site uses cookies to store information on your computer.

Some cookies on this site are essential, and the site won't work as expected without them. These cookies are set when you submit a form, login or interact with the site by doing something that goes beyond clicking on simple links.

By using our site you accept the terms of our Privacy Policy.

(One cookie will be set to store your preference)
(Ticking this sets a cookie to hide this popup if you then hit close. This will not store any personal information)

About this tool

About Cookie Control

You are here

Historical Interest Only

This is a static HTML version of an old Drupal site. The site is no longer maintained and could be deleted at any point. It is only here for historical interest.

Graph Colouring Heuristics Guided by Higher Order Graph Properties

TitleGraph Colouring Heuristics Guided by Higher Order Graph Properties
Publication TypeConference Paper
Year of Publication2008
AuthorsJuhos, I\'{a}n, van Hemert, J
Conference NameLecture Notes in Computer Science
PublisherSpringer
Editorvan Hemert, J, Cotta, C
Keywordsevolutionary computation; graph colouring
Abstract

Graph 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.

Full Text