A generalized implicit enumeration algorithm for graph coloring
Authors:
Open Access
- 1 April 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 28 (4) , 412-418
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 8 references indexed in Scilit:
- An improved transitive closure algorithmComputing, 1983
- 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
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- An Algorithm for Coloring the Vertices of an Arbitrary Finite Graph1973
- Chromatic Scheduling and the Chromatic Number ProblemManagement Science, 1972