A generalized implicit enumeration algorithm for graph coloring
- 1 April 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 28 (4) , 412-418
- https://doi.org/10.1145/3341.3350
Abstract
A generalized algorithm for graph coloring by implicit enumeration is formulated. A number of backtracking sequential methods are discussed in terms of the generalized algorithm. Some are revealed to be partially correct and inexact. A few corrections to the invalid algorithms, which cause these algorithms to guarantee optimal solutions, are proposed. Finally, some computational results and remarks on the practical relevance of improved implicit enumeration algorithms are given.Keywords
This publication has 6 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- A correction to Brelaz's modification of Brown's coloring algorithmCommunications of the ACM, 1983
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-completeDiscrete Mathematics, 1980
- New methods to color the vertices of a graphCommunications of the ACM, 1979
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- An Algorithm for Coloring the Vertices of an Arbitrary Finite GraphPublished by Springer Nature ,1973