Summary
Graph vertex colouring can be defined in such a way where colour assignments are substituted by vertex contractions. We present various hypergraph representations for the graph colouring problem all based on the approach where vertices are merged into groups. In this paper, we explain this approach and identify three reasons that make it useful. First, generally, this approach provides a potential decrease in computational complexity. Second, it provides a uniform and compact way in which algorithms, be it of a complete or a heuristic nature, can be defined and progress toward a colouring. Last, it opens the way to novel applications that extract information useful to guide algorithms during their search. These approaches can be useful in the design of an algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Juhos, I., van Hemert, J. (2008). Contraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem. In: Cotta, C., van Hemert, J. (eds) Recent Advances in Evolutionary Computation for Combinatorial Optimization. Studies in Computational Intelligence, vol 153. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70807-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-70807-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70806-3
Online ISBN: 978-3-540-70807-0
eBook Packages: EngineeringEngineering (R0)