Tackling the edge dynamic graph colouring problem with and without future adjacency information

Hardy, Bradley, Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X and Thompson, Jonathan 2018. Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics 24 , pp. 321-343. 10.1007/s10732-017-9327-z

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (684kB) | Preview

Abstract

Many real world operational research problems, such as frequency assignment and exam timetabling, can be reformulated as graph colouring problems (GCPs). Most algorithms for the GCP operate under the assumption that its constraints are fixed, allowing us to model the problem using a static graph. However, in many real-world cases this does not hold and it is more appropriate to model problems with constraints that change over time using an edge dynamic graph. Although exploring methods for colouring dynamic graphs has been identified as an area of interest with many real-world applications, to date, very little literature exists regarding such methods. In this paper we present several heuristic methods for modifying a feasible colouring at time-step t into an initial, but not necessarily feasible, colouring for a “similar” graph at time-step t+1t+1 . We will discuss two cases; (1) where changes occur at random, and (2) where probabilistic information about future changes is provided. Experimental results are also presented and the benefits of applying these particular modification methods are investigated.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Additional Information:	This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher:	Springer Verlag (Germany)
ISSN:	1381-1231
Funders:	EPSRC
Date of First Compliant Deposit:	5 April 2017
Date of Acceptance:	20 March 2017
Last Modified:	12 Apr 2024 12:41
URI:	https://orca.cardiff.ac.uk/id/eprint/99658

Citation Data

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

Actions (repository staff only)

Edit Item