This file briefly describes the input data and generators available at DIMACS ftp site (dimacs.rutgers.edu). We will continue to collect further information and strongly encourage you to contribute input generators and benchmark instances. I. N-body problems * GENERATOR pub/challenge3/n-body/generator This directory contains an input generator for N-body problem. It can generator uniform distributions, a Plummer model, or two nearby Plummer models. This code is based on a generator by J. Barnes. II. Graphs * FORMATS pub/challenge/graph/doc Discussion of DIMACS Challenge graph format. See ccformat.tex for details. pub/challenge/graph/translators Translators for different grpah formats. * INSTANCES pub/challenge/graph/benchmarks/{clique,color} Input graphs for clique and chromatic number problems (from Challenge II). See contents.tex for details. pub/dsj/{clique,chrom} Similar data provided by David Johnson. See code.readme*, README for details. pub/dsj/partition Input grpahs for partitioning problem. * GENERATORS pub/netflow/generators This directory contains programs that generate networks and graphs. Most are in the DIMACS format. This Directory Contains: universal.c : A very portable random number generator, as C-language function calls. Read the in-line code. matching/ : A directory of generators for matching problems. network/ : A directory containing generators for network problems. pub/netflow/generators/matching This directory contains instance generators for matching problems. asnmat.a : Awk program to convert DIMACS .asn format to .edge format. clusters.c : Generates points within a circle which are clustered according to some input parameters. Documentation is in code. To compile: cc clusters.c -lm dcube.c : Generates points uniform within a d-dimensional cube. Documentation is in the code. hardcard.f : Generates (nongeometric) graphs which Gabow has shown will be hard for Edmond's cardinality matching algorithm. Provided by R. B. Mattingly. This is a Fortran program. To compile: f77 hardcard.f neighbor.c : Takes a graph in .geom format and a command line argument k. Produces a graph in .edge format. Vertex i is has an edge to vertices [i-k, i-1]. See the code for more documentation. NOTE: a version which includes the p line and which is slightly more robust was installed July 26. random.c : Generates a random undirected graph with m edges. Edge weights are uniformly distributed within a specified range. See the code for further documentation. NOTE: the original version contains a bug. The fixed version was installed July 22. t.f : Generates a sequence of K one-connected triangles in .edge format. Written in Fortran. These graphs tend to generate a lot of blossoms. Contributed by N. Ritchey and B. Mattingly tt.f : Generates a sequence of K tri-connected triangles in .edge format. Written in Fortran. Contributed by N. Ritchey and B. Mattingly fractals/ : Subdirectory containing generators of fractal-like instances, in .geom format.