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

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

Hardy, Bradley, Lewis, Rhyd and Thompson, Jonathan Mark 2018. Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics 24 (3) , pp. 321-343. 10.1007/s10732-017-9327-z

[img]
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
Publisher: Springer Verlag (Germany)
ISSN: 1381-1231
Funders: EPSRC
Last Modified: 24 Jul 2018 13:16
URI: http://orca.cf.ac.uk/id/eprint/99658

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics