doi: 10.4304/jsw.1.2.24-33
Increasing the efficiency of graph colouring algorithms with a representation based on vector operations
- 1 Department of Computer Algorithms and Artificial Intelligence, University of Szeged, Hungary
- 2 National e-Science Institute, University of Edinburgh, United Kingdom
Abstract
We introduce a novel representation for the graphcolouring problem, called the Integer Merge Model, whichaims to reduce the time complexity of graph colouringalgorithms. Moreover, this model provides useful informationto aid in the creation of heuristics that can make thecolouring process even faster. It also serves as a compactdefinition for the description of graph colouring algorithms.To verify the potential of the model, we use it in the completealgorithm DSATUR, and in two version of an incompleteapproximation algorithm; an evolutionary algorithm andthe same evolutionary algorithm extended with guidingheuristics. Both theoretical and empirical results are providedinvestigation is performed to show an increase in theefficiency of solving graph colouring problems. Two problemsuites were used for the empirical evidence: a set of practicalproblem instances and a set of hard problem instances fromthe phase transition.
Keywords
- graph colouring
- representation
- node me
How to Cite
Istv´an Juhos and Jano I. van Hemert, "Increasing the efficiency of graph colouring algorithms with a representation based on vector operations," Journal of Software, vol. 1, no. 2, pp. 24-33, 2006. https://doi.org/ 10.4304/jsw.1.2.24-33
Copyright & License
Copyright © 2006 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).