Skip to main navigation Skip to search Skip to main content

An analysis of heuristics for vertex colouring

  • Université Libre de Bruxelles

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

Several heuristics have been presented in the literature for finding a proper colouring of the vertices of a graph using the least number of colours. These heuristics are commonly compared on a set of graphs that served two DIMACS competitions. This set does not permit the statistical study of relations between algorithm performance and structural features of graphs. We generate a new set of random graphs controlling their structural features and advance the knowledge of heuristics for graph colouring. We maintain and make all algorithms described here publically available in order to facilitate future comparisons.
Original languageEnglish
Title of host publicationExperimental Algorithms : Proceedings of the 9th International Symposium, (SEA 2010)
EditorsPaola Festa
PublisherSpringer
Publication date2010
Pages326-337
ISBN (Print)978-3-642-13192-9
ISBN (Electronic)978-3-642-13192-9
DOIs
Publication statusPublished - 2010
EventAn analysis of heuristics for vertex colouring - Napoles, Italy
Duration: 24. Aug 2010 → …

Conference

ConferenceAn analysis of heuristics for vertex colouring
Country/TerritoryItaly
CityNapoles
Period24/08/2010 → …
SeriesLecture Notes in Computer Science
Volume6049

Fingerprint

Dive into the research topics of 'An analysis of heuristics for vertex colouring'. Together they form a unique fingerprint.

Cite this