Notes:

Reg

(From Gary Lewandowski gary@cs.wisc.edu Problem based on register allocation for variables in real codes. For more instances, see the programs and data in graph/contributed/lewandowski.

Lei

(From Craig Morgenstern morgenst@riogrande.cs.tcu.edu) Leighton graphs with guaranteed coloring size. A reference is F.T. Leighton, Journal of Research of the National Bureau of Standards, 84: 489-505 (1979). For many more instances and programs, see the work in graph/contributed/morgenstern.

Cul

(From Joe Culberson joe@cs.ualberta.ca) Quasi-random coloring problem. For generator, and further information, see program and README.gen in graph/contributed/culberson.

Sch

(From Gary Lewandowski lewandow@cs.wisc.edu) Class scheduling graphs, with and without study halls.

Lat

(From Gary Lewandowski lewandow@cs.wisc.edu) Latin square problem.

DSJ

(From David Johnson dsj@research.att.com) Random graphs used in his paper with Aragon, McGeoch, and Schevon, ``Optimization by Simulated Annelaing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning'', Operations Research, 31, 378-406 (1991). DSJC are standard (n,p) random graphs. DSJR are geometric graphs, with DSJR..c being complements of geometric graphs.

• About this document ...