Exact coloring of real-life graphs is easy

ABSTRACT

Graph coloring has several important applications inVLSI CAD. Since graph coloring is NP-complete, heuristics are used to approximate the optimum solution. But heuristic solutions are typically 10% off, and as much as100% off, the minimum coloring. This paper shows thatsince real-life graphs appear to be 1-perfect, one can indeed solve them exactly for a small overhead.

REFERENCES

• 1: M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
• 2: B. Bollob~s, P. ErdSs, "Cliques in Random Graphs", Math. Proc. Camb. Phil. Soc., 80, pp. 419-427, 1976.
• 3: B. Bollob~s, "The Chromatic Number of Random Graphs", Combinatorica, 8-1, pp. 49-55, 1988.
• 4: 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]
• 5: J. R. Brown, "Chromatic Scheduling and the Chromatic Number Problem", Management Sci., 19, pp. 456-463, 1972.
• 6: J. Cong, M. Hossain, N. A. Sherwani, "A Provably Good Multilayer Topological Planar Routing Algorithm in IC Layout Designs", IEEE Trans. on CAD, 12-1, pp. 70-78, Jan. 1993.
• 7: ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmark/, benchmark for graph coloring and clique, 1993.
• 8: D. Gajski, N. Dutt, A. Wu, S. Lin, High-Level Synthesis, Kluwer Ac. Pub., 1992.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: M. GrSetschel, L. Lovgsz, A. Schrijver, ~The Ellipsoid Method and its Consequences in Combinatorial Optimization", Combinatorica, 1, pp. 169-197, 1981.
• 11: Magnús M. Hallórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters, v.45 n.1, p.19-23, Jan. 25, 1993 [doi>10.1016/0020-0190(93)90246-6]
• 12: D. S. Johnson, ~Worst-Case Behavior of Graph-Coloring Algorithms", Proc. 5th Southeastern Conf. on Uombinatorics, Graph Theory, and Computing, pp. 513-528, Winnipeg, 1974.
• 13: L. Kueera, Combinatorial Algorithms, Adam Hilger, 1990.
• 14: F. T. Leighton, ~A Graph Coloring Algorithm for Large Scheduling Problems", Y. Res. Nat. Bur. Standards, 84, pp. 489-506, 1979.
• 15: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 16: C. A. Morgenstern, Algorithms for General Graph Coloring, Ph.D. thesis, Department of Computing Science, University of New Mexico, Albuquerque NM, 1990.
• 17: J. Mycielski, ~Sur le Coloriage des Graphes", Colloq. Math., 3, 1955
• 18: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  J. Computer Applications

General Terms:
Design, Measurement, Performance, Theory, Verification