A generalized implicit enumeration algorithm for graph coloring

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.

REFERENCES

• 1: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 2: Brown, R.J. Chromatic scheduling and the chromatic number problem. Manage. Sri. 19,4 (Dec. 1972). 451-463.
• 3: Nicos Christofides, Graph theory: An algorithmic approach (Computer science and applied mathematics), Academic Press, Inc., Orlando, FL, 1975
• 4: Dailey, D.P. Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Math. 30, (1980), 269-293.
• 5: Diirre, K. An algorithm for coloring the vertices of an arbitrary graph. In Lecture Notes in Economics and Mathematical Sysfems. Vol. 78. P. Deussen Ed., Springer-Verlag, Berlin, 1973, pp. 82-89.
• 6: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 7: Garey. M.R.. Johnson, D.S.. and Stockmeyer, L. Some simplified NP- complete graph problems. Theor. Comput. Sci. I, (1976). 237-267.
• 8: Horowitz. E.. and Sahni. S. Fundamentals ofcomputer Algorithms. Computer Science, Potomac. Md.. 1978, pp. 614-621.
• 9: Korman, SM. The graph-colouring problem. In Combinatorial Optimization. N. Christofides. A. Mingozzi, P. Toth, and C. Sandi. Eds., Wiley, New York, 1979. pp. 211-235.
• 10: Kubale. M.. and Kusz. E. Computational experience with implicit enumeration algorithms for graph coloring. In Proceedings of the WG'83 International Workshop on Graphtheoretic Concepts in Computer Science. M. Nag1 and J. Perl, Eds., Trauner Verlag. Linz, 1983, pp. 167-176.
• 11: Jürgen Peemöller, A correction to Brelaz's modification of Brown's coloring algorithm, Communications of the ACM, v.26 n.8, p.595-597, Aug. 1983 [doi>10.1145/358161.358171]
• 12: Schmitz, L. An improved transitive closure algorithm. Computing 30. 4 (1983). 359-371.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

General Terms:
Algorithms, Measurement, Performance, Theory