Abstract
Graph vertex colouring can be defined in such a way where colour assignments are substituted by vertex contractions. We present various hyper-graph representations for the graph colouring problem all based on the approach where vertices are merged into groups. In this paper, we show this provides a uniform and compact way to define algorithms, both of a complete or a heuristic nature. Moreover, the representation provides information useful to guide algorithms during their search. In this paper we focus on the quality of solutions obtained by graph colouring heuristics that make use of higher order properties derived during the search. An evolutionary algorithm is used to search permutations of possible merge orderings.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Craenen, B., Eiben, A., van Hemert, J.: Comparing evolutionary algorithms on binary constraint satisfaction problems. IEEE Transactions on Evolutionary Computation 7, 424–444 (2003)
Juhos, I., van Hemert, J.: Improving graph colouring algorithms and heuristics by a novel representation. In: Proceeding of the Evolutionary Computation in Combinatorial Optimization, 6th European Conference, pp. 123–134 (2006)
Culberson, J., Gent, I.: Frozen development in graph coloring. Theor. Comput. Sci. 265, 227–264 (2001)
Juhos, I., van Hemert, J.: Increasing the efficiency of graph colouring algorithms with a representation based on vector operations. Journal of Software 1, 24–33 (2006)
Dutton, R.D., Brigham, R.C.: A new graph coloring algorithm. Computer Journal 24, 85–86 (1981)
Graham, R.L., Grötschel, M., Lovász, L. (eds.): Handbook of combinatorics, vol. 1. MIT Press, Cambridge (1995)
Wilf, H.S.: The eigenvalues of a graph and its chromatic number, J. london. London Math. Soc., 330–332 (1967)
Merikoski, J.K., Kumar, R.: Lower bounds for the spectral norm. Journal of Inequalities in Pure and Applied Mathematics 6 (2005)
Bäck, T., Fogel, D., Michalewicz, Z. (eds.): Handbook of Evolutionary Computation. Institute of Physics Publishing Ltd, Bristol and Oxford University Press, Oxford (1997)
Culberson, J.: Iterated greedy graph coloring and the difficulty landscape. Technical Report tr 92-07, University of Alberta, Dept. of Computing Science (1992)
Coudert, O.: Exact coloring of real-life graphs is easy. In: DAC 1997: Proceedings of the 34th annual conference on Design automation, pp. 121–126. ACM, New York (1997)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Juhos, I., van Hemert, J. (2008). Graph Colouring Heuristics Guided by Higher Order Graph Properties. In: van Hemert, J., Cotta, C. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2008. Lecture Notes in Computer Science, vol 4972. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78604-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-78604-7_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78603-0
Online ISBN: 978-3-540-78604-7
eBook Packages: Computer ScienceComputer Science (R0)