Almost all k-colorable graphs are easy to color |
| |
Affiliation: | 2. Moscow Institute of Physics and Technology, Dolgoprudniy, Russia;3. École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland;1. Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, Brazil;2. Fachbereich Mathematik, Universität Hamburg, Hamburg, Germany;3. Institut für Mathematik, Technische Universität Hamburg–Harburg, Hamburg, Germany |
| |
Abstract: | We describe a simple and efficient heuristic algorithm for the graph coloring problem and show that for all k ≥ 1, it finds an optimal coloring for almost all k-colorable graphs. We also show that an algorithm proposed by Brélaz and justified on experimental grounds optimally colors almost all k-colorable graphs. Efficient implementations of both algorithms are given. The first one runs in O(n + m log k) time where n is the number of vertices and m the number of edges. The new implementation of Brélaz's algorithm runs in O(m log n) time. We observe that the popular greedy heuristic works poorly on k-colorable graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|