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

Dyfyniad
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


Hawliau Mynediad: Gall data fod ar gael yn rhad ac am ddim yn amodol ar briodoli
Dull Mynediad: I anfon cais i gael y data hwn, ebostiwch opendata@caerdydd.ac.uk

Crewyr y Set Ddata o Brifysgol Caerdydd

Manylion y Set Ddata
Cyhoeddwr: Cardiff University
Dyddiad (y flwyddyn) pryd y daeth y data ar gael i'r cyhoedd: 2017
Fformat y data: .CSV, .TXT
Amcangyfrif o gyfanswm maint storio'r set ddata: Llai na 100 megabeit
DOI: 10.17035/d.2017.0033322283

Disgrifiad

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

Diweddarwyd y tro diwethaf ar 2019-22-07 am 15:43