Lewis, Rhyd  ORCID: https://orcid.org/0000-0003-1046-811X, Thompson, Jonathan Mark, Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 and Gillard, Jonathan William ORCID: https://orcid.org/0000-0001-9166-298X
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
|
Preview |
Text
- Accepted Post-Print Version
Download (519kB) | Preview |
Abstract
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: | Schools > Mathematics Schools > 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: | 08 Jan 2025 11:49 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/11330 |
Citation Data
Cited 26 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |
Dimensions
Dimensions