Title: Data supporting results concerning colourings for the edge dynamic graph colouring problem with and without future adjacency information

Citation
Hardy B, Lewis R, Thompson J (2017). Data supporting results concerning colourings for the edge dynamic graph colouring problem with and without future adjacency information. Cardiff University. http://doi.org/10.17035/d.2017.0033322283


Access Rights: Data can be made freely available subject to attribution
Access Method: Click to email a request for this data to opendata@cardiff.ac.uk

Cardiff University Dataset Creators

Dataset Details
Publisher: Cardiff University
Date (year) of data becoming publicly available: 2017
Data format: .CSV, .TXT
Estimated total storage size of dataset: Less than 100 megabytes
DOI: 10.17035/d.2017.0033322283

Description

The graph colouring problem (GCP) is a well-studied combinatorial optimisation problem that is known to be NP-hard. Most algorithms for solving the GCP do not consider the possibility of a graph changing over time. In our research, we consider a dynamic version of the graph colouring problem in which the edge set is allowed to change. By considering a dynamic graph as a series of static graphs, our approach takes a feasible colouring for the static-representation of a dynamic graph at one time-step and modifies it in some way to be used as an initial, though not necessarily feasible, colouring for the static-representation of the dynamic graph in the following time-step. We consider two situations; firstly, where the changes occur at random, and secondly, where probabilistic information regarding future change is known.


Data related to our experiments are available in .CSV files which provides information regarding the test instances used and the outputs of our algorithms. Four different modification operators were used within our algorithm, three of which were also combined with a secondary optimisation stage concerning the probabilistic future change information. Explicit description of the data sets are also provided in .TXT files.

The accompanying publication has the following DOI: 10.1007/s10732-017-9327-z

Last updated on 2019-22-07 at 15:43