MARCO GSRC Calibrating Achievable Design: Bookshelf

Graph Coloring

(see other slots)

work in progress: last updated Sat May 2000

Darko Kirovski and Miodrag Potkonjak

Contents

I. Introduction and overview
II. DIMACS Standard Graph Coloring Formats
III. Publicly available instances, solutions and reference performance results
IV. Executable Utilities (in preparation)
V. Performance results
VI. Implementations (source code and executables) of graph coloring solvers

I. Introduction and overview

Graph (vertex) coloring problem plays a very important role in theoretic graph theory and finds many applications in real life. For example, the register allocation problem, the class scheduling problem, the cache-line coloring problem, wavelength assignment in optical networks, and channel assignment in cellular systems. In the monograph "Graph Colourings" edited by R. Nelson and R.J. Wilson (Longman Scientific & Technical, Harlow,Essex, UK 1990), Toft stated 75 interesting and easily-formulated graph coloring problems. In 1992, DIMACS included graph coloring as one of the three NP hard problems (the other two are maximum clique and satisfiability) for its second implementation challenge. Detail information, includes the FTP site and selected papers, can be found at DIMACS implementation challenges site.

II. DIMACS Standard Graph Coloring Formats

Quite a few research papers have been referring to the DIMACS graph format. Here we use the specification for undirected graph. More information about the DIMACS graph format can be found in the DIMACS Implementation Challenges site.

III. Publicly available instances, solutions and reference performance results

This links list the graph coloring benchmarks for both random graphs and graphs derived from real-life problems, such as register allocation for variables in real codes, class scheduling graphs, and Latin square problem. Most instances are in DIMACS standard format, they involve vertices ranging from 11 to 1000, the optimal coloring requires colors from 4 to 76, and some of them are still open, especially for the random graphs.

IV. Executable Utilities (in preparation)

V. Performance results

The known optimal colorings for the benchmarks are list with the instances. The real-life graphs, in particular the graphs from register allocation problems are easy to color in general. While solutions for random graph, especially the one with 1,000 vertices and an edge probability slightly larger than 0.5 (known as the DIMACS challenge graph, instance DSJC1000.5) are still open.

VI. Implementation (source code and executables): download

darko@cs.ucla.edu,miodrag@cs.ucla.edu,imarkov@cs.ucla.edu