Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A wide-ranging computational comparison of high-performance graph colouring algorithms

Lewis, Rhyd ORCID:, Thompson, Jonathan Mark, Mumford, Christine Lesley ORCID: and Gillard, Jonathan William ORCID: 2012. A wide-ranging computational comparison of high-performance graph colouring algorithms. Computers & Operations Research 39 (9) , pp. 1933-1950. 10.1016/j.cor.2011.08.010

[thumbnail of LewisWide-RangingComputational2012.pdf]
Text - Accepted Post-Print Version
Download (519kB) | Preview


This paper reviews the current state of the literature surrounding methods for the general graph colouring problem and presents a broad comparison of six high-performance algorithms, each belonging to one of the main algorithmic schemes identified. Unlike many previous computational studies in graph colouring, a large range of both artificially generated and real-world graphs are considered, culminating in over 40,000 individual trials that have consumed more than a decade of computation time in total. The picture painted by the comparison is complex, with each method outperforming all others on at least one occasion; however, general patterns are also observed, particularly with regards to the advantages of hybridising local-search techniques with global-based operators.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Computer Science & Informatics
Subjects: Q Science > QA Mathematics
Uncontrolled Keywords: Graph colouring; Metaheuristics; Combinatorial optimisation
Publisher: Elsevier
ISSN: 0305-0548
Date of First Compliant Deposit: 30 March 2016
Last Modified: 03 Apr 2024 04:51

Citation Data

Cited 25 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics