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

DOI URL: http://doi.org/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