DIMACS is the NSF Science and Technology center for Discrete Mathematics and Theoretical Computer Science, based at Rutgers University. Each year they sponsor an implementation challenge workshop to stimulate research in empirical algorithms research. Each year has a different theme, resulting in implementations for a different class of problems. Proceedings volumes for each workshop are published in the DIMACS series by the American Mathematical Society (AMS).

The First DIMACS Implementation Challenge on Network Flows and Matching in October 1991. Several implementations for maximum weight and maximum cardinality matching were collected and can be obtained by anonymous ftp from dimacs.rutgers.edu in the directory pub/netflow/matching. These include:

- A maximum cardinality matching solver in Fortran 77 by R. Bruce Mattingly %(FR132601@ysub.ysu.edu) and Nathan P. Ritchey (nate@macs.ysu.edu) of the Youngstown State University, which seems capable of solving instances of 5,000 nodes and 60,000 edges in under 30 seconds.
- A maximum cardinality matching solver in C by Edward Rothberg (rothberg@sgi.com) of Silicon Graphics, which implements Gabow's \cite{Gabow-76} $O(n^3)$ algorithm.
- A maximum weighted matching solver in C by Edward Rothberg. This is slower than his unweighted solver described above, but obviously more general. For example, it took over 30 seconds on a weighted graph with 500 nodes and 4,000 edges.
- A preflow-push network flow implementation in C language by Edward Rothberg of Silicon Graphics (rothberg@sgi.com). It took under a second on a test graph of 500 nodes and 4,000 edges, but over an hour with 5,000 nodes and 40,000 edges.
- An implementation of 11 network flow variants in C, including the older Dinic and Karzanov algorithms by Richard Anderson (anderson@cs.washington.edu) and Joao Setubal of the University of Washington. On an instance of 8,000 vertices and 12,000 edges, all options finished within two seconds.

Programs for the closely related problems of finding cliques, chromatic number, and independent sets were also sought for the second DIMACS challenge. The programs and data from the challenge are available by anonymous ftp from dimacs.rutgers.edu. Source codes are available under pub/challenge/graph and test data under pub/djs. In particular, two C language programs by David S. Johnson and David L. Applegate are available:

- The dfmax.c implements a simple-minded branch-and-bound algorithm very similar to that of Carraghan and Paradalos. for cliques which should perform well on sparse graphs.
- The dmclique.c is a variant on the simple `semi-exhaustive greedy' scheme for finding large independent sets used in the graph coloring algorithm XRLF. nmclique.c is a new version of dmclique.c that prints out the best clique found.

Performance data on both programs is available in files results.dfmax and results.dmclique within the directories /pub/challenge/graph/benchmarks/clique and /pub/challenge/graph/benchmarks/volume.

Also included in the Second DIMACS Implementation Challenge was satisfiablity.
Programs and data from the challenge are available by anonymous ftp
from dimacs.rutgers.edu in the directory /pub/challenge/sat.
In particular, there is
SATO,
a satisfiability solver
by Hantao Zhang, and
a random formula generator named mwff.c
for constructing hard satisfiability instances in C by Bart Selman

The Third DIMACS challenge, held in 1994, focused on parallel algorithms for graphs and game-tree search.

The Fourth DIMACS challenge, held in 1995, focused on two problems in computational biology; fragment assembly and sorting with reversals.

The Fifth DIMACS implementation challenge in 1996 will focus on elementary data structures like dictionaries. The world's best available dictionary implementations are likely to be identified in the course of the challenge.

Clique (9) |
Matching (9) |
Kd-Trees (8) |

Network Flow (8) |
Shortest Path (8) |
Vertex Coloring (7) |

Independent Set (5) |
Satisfiability (5) |
Vertex Cover (4) |

Dictionaries (1) |
Kd-Trees (1) |
Priority Queues (1) |

This page last modified on 2008-07-10 . www.algorist.com