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

On the application of graph colouring techniques in round-robin sports scheduling

Lewis, Rhyd and Thompson, Jonathan Mark 2011. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research 38 (1) , pp. 190-204. 10.1016/j.cor.2010.04.012

[img]
Preview
PDF - Submitted Pre-Print Version
Download (526kB) | Preview

Abstract

The purpose of this paper is twofold. First, it explores the issue of producing valid, compact round-robin sports schedules by considering the problem as one of graph colouring. Using this model, which can also be extended to incorporate additional constraints, the difficulty of such problems is then gauged by considering the performance of a number of different graph colouring algorithms. Second, neighbourhood operators are then proposed that can be derived from the underlying graph colouring model and, in an example application, we show how these operators can be used in conjunction with multi-objective optimisation techniques to produce high-quality solutions to a real-world sports league scheduling problem encountered at the Welsh Rugby Union in Cardiff, Wales.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords: Metaheuristics; Sports scheduling; Graph colouring; Timetabling
Publisher: Elsevier
ISSN: 0305-0548
Last Modified: 04 Jun 2017 02:21
URI: http://orca.cf.ac.uk/id/eprint/11081

Citation Data

Cited 20 times in Google Scholar. View in Google Scholar

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

Cited 5 times in Web of Science. View in Web of Science.

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics