Efficient coloring of a large spectrum of graphs

ABSTRACT

We have developed a new algorithm and software for graph coloring by systematically combining several algorithm and software development ideas that had crucial impact on the algorithm's performance. The algorithm explores the divide-and-conquer paradigm, global search for constrained independent sets using a computationally inexpensive objective function, assignment of most-constrained vertices to least-constraining colors, reuse and locality exploration of intermediate solutions, search time management, post-processing lottery-scheduling iterative improvement, and statistical parameter determination and validation. The algorithm was tested on a set of real-life examples. We found that hard-to-color real-life examples are common especially in domains where problem modeling results in denser graphs. Systematic experimentations demonstrated that for numerous instances the algorithm outperformed all other implementations reported in literature in solution quality and run-time.

REFERENCES

• Bol85: Bollobas, B.,Thomason, A. RandomGraphsof Small Order. Annalsof Disc. Math., vol.28, pp. 47-57, 1985
• Bre79: 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]
• Cha87: Crams, M,, et al. Some Experiments With Simulated Annealing for Coloring Graphs, European Journal of Gperations Research, vol.32, pp.260-66,1987.
• Cou97: Olivier Coudert, Exact coloring of real-life graphs is easy, Proceedings of the 34th annual conference on Design automation, p.121-126, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266047]
• Fle96: Fleurent, C,, Ferland, J.A. Genetic and hybrid algorithms for graph coloring. Annals of Gperations Research, vol.63, pp.437-461, 1996.
• Gar79: 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
• Hal93: 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]
• Her87: A. Hertz , D. de Werra, Using tabu search techniques for graph coloring, Computing, v.39 n.4, p.345-351, Dec. 1987 [doi>10.1007/BF02239976]
• Joh91: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Operations Research, v.39 n.3, p.378-406, May-June 1991 [doi>10.1287/opre.39.3.378]
• Jue96: Ari Juels , Marcus Peinado, Hidden Cliques as Cryptographic Keys, University of California at Berkeley, Berkeley, CA, 1996
• Kir98: Kirovsld, D., Potkonjak, M. Exact Coloring of Many Real-Life Graphs is Dif. licult, but Heuristic Coloring is Almost Always Effective. Technical Report, CSD, UCLA, 1997.
• Lei79: Leighton, F.T. A Graph Coloring Algorithm for Large Scheduling Algorithms. Journal of Res. Natl. Bur. Standards, vol.84, pp.489-506, 1979.
• Mor86: Morgenstern,C,,Shapiro,H.ChromaticNumberApproximationUsing $imulatedAnnealing.Unpublished,1986.
• Mor94: Morgenstern, C. Distributed Coloration Neighborhood Search. DIMACS Series in Disc. Math., vol,0,1994.
• Pee83: 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]
• Wal94: Waldspurger, C.A.; Weihl, W.E. Lottery scheduling: flexible ixoportionalshare resource management. The First USENIX Symposium on Operating Systems Design and Implementation, pp. 1-11, 1994.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
ISM frequency band, RF CMOS, digital radio, spread spectrum communication, transceiver