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

Heuristic methods for colouring dynamic random graphs

Hardy, Bradley 2018. Heuristic methods for colouring dynamic random graphs. PhD Thesis, Cardiff University.
Item availability restricted.

[img]
Preview
PDF - Accepted Post-Print Version
Download (1MB) | Preview
[img] PDF - Supplemental Material
Restricted to Repository staff only

Download (203kB)

Abstract

Many real-world operational research problems can be reformulated into static graph colouring problems. However, such problems might be better represented as dynamic graphs if their size and/or constraints change over time. In this thesis, we explore heuristics approaches for colouring dynamic random graphs. We consider two different types of dynamic graph: edge dynamic and vertex dynamic. We also consider two different change scenarios for each of these dynamic graph types: without future change information (i. e. random change) and with probabilistic future change information. By considering a dynamic graph as a series of static graphs, we propose a modi fication approach which modifies a feasible colouring (or solution) for the static representation of a dynamic graph at one time-step into a colouring for the subsequent time-step. In almost all cases, this approach is beneficial with regards to either improving quality or reducing computational effort when compared against using a static graph colouring approach for each time-step independently. In fact, for test instances with small amounts of change between time-steps, this approach can be beneficial with regards to both quality and computational effort When probabilistic future change information is available, we propose a twostage approach which first attempts to identify a feasible colouring for the current time-step using our modification approach, and then attempts to increase the robustness of the colouring with regards to potential future changes. For both the edge and vertex dynamic cases, this approach was shown to decrease the problematic change introduced between time-steps. A clear trade-off can be observed between the quality of a colouring and its potential robustness, such that a colouring with more colours (i. e. reduced quality) can be made more robust.

Item Type: Thesis (PhD)
Status: Unpublished
Schools: Mathematics
Date of First Compliant Deposit: 1 March 2018
Date of Acceptance: February 2018
Last Modified: 12 Apr 2021 15:29
URI: http://orca.cf.ac.uk/id/eprint/109385

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics