The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

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 in the directory pub/netflow/matching. These include:

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 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:

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 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 Webpage
  • Dimacs Challenges Website

    Problem Links

    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 .