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 di�erent types of dynamic graph: edge dynamic and vertex dynamic. We also consider two di�erent 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 �cation approach� which modi�es 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 bene�cial with regards to either improving quality or reducing computational e�ort 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 bene�cial with regards to both quality and computational e�ort When probabilistic future change information is available, we propose a �twostage approach� which �rst attempts to identify a feasible colouring for the current time-step using our �modi�cation 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-o� 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: 01 Mar 2018 09:13
URI: http://orca-mwe.cf.ac.uk/id/eprint/109385

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics