RAPID - Robust and Accurate Polygon Interface detection
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.
Download Files (local site)dimacs WebpageDimacs Challenges Website
Problem Links
This page last modified on 2008-07-10
.
www.algorist.com
