Modifying colourings between time-steps to tackle changes in dynamic random graphs

Hardy, Bradley, Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X and Thompson, Jonathan Mark 2016. Modifying colourings between time-steps to tackle changes in dynamic random graphs. Presented at: EvoCOP 2016: European Conference on Evolutionary Computation in Combinatorial Optimization, Porto, Portugal, 30 March - 1 April 2016. Published in: Chicano, Francisco, Hu, Bin and Garcia-Sanchez, Pablo eds. Evolutionary Computation in Combinatorial Optimization: 16th European Conference, EvoCOP 2016, Porto, Portugal, March 30 – April 1, 2016, Proceedings. Lecture Notes in Computer Science. , vol.9595 Springer, pp. 186-201. 10.1007/978-3-319-30698-8_13

Preview

PDF - Accepted Post-Print Version Download (1MB) | Preview

Abstract

Many real world operational research problems can be formulated as graph colouring problems. Algorithms for this problem usually operate under the assumption that the size and constraints of a problem are fixed, allowing us to model the problem using a static graph. For many problems however, this is not the case and it would be more appropriate to model such problems using dynamic graphs. In this paper we will explore whether feasible colourings for one graph at time-step t can be modified into a colouring for a similar graph at time-step t+1 in some beneficial manner.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Publisher:	Springer
ISBN:	9783319306971
ISSN:	0302-9743
Date of First Compliant Deposit:	30 March 2016
Date of Acceptance:	2016
Last Modified:	08 Jan 2025 12:00
URI:	https://orca.cardiff.ac.uk/id/eprint/88108

Citation Data

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

Actions (repository staff only)

Edit Item