For a more detailed treatment of applications and solution techniques, the
interested reader is referred to the surveys of
Fortunato2, Schaeffer3,
and Schloegel
on the different topics.
Within the algorithms community, techniques for solving the problems above
have been developed at least since the early 1970s—while some of the applications
are newer. Improving known and developing new solution techniques are aspects
of ongoing research.
The primary goal of this challenge was to create a reproducible picture of the
state of the art in the area of graph partitioning and graph clustering algorithms. To
this end, a standard set of benchmark instances was identified. Then participants
were invited to submit solutions to different challenge problems. This way differ-
ent algorithms and implementations were tested against the benchmark instances.
Thereby future researchers are enabled to identify techniques that are most effec-
tive for a respective partitioning or clustering problem—by using our benchmark
set and by comparing their results to the challenge results.
2. Key Results
The main results of the 10th DIMACS Implementation Challenge include:
Extension of a file format used by several graph partitioning and graph
clustering libraries for graphs, their geometry, and partitions. Formats
are described on the challenge website.5
Collection and online archival5 of a common testbed of input instances
and generators (including their description) from different categories for
evaluating graph partitioning and graph clustering algorithms. For the
actual challenge, a core subset of the testbed was chosen.
Definition of a new combination of measures to assess the quality of a
Definition of a measure to assess the work an implemention performs in a
parallel setting. This measure is used to normalize sequential and parallel
implementations to a common base line.
Experimental evaluation of state-of-the-art implementations of graph par-
titioning and graph clustering codes on the core input families.
A nondiscriminatory way to assign scores to solvers that takes both run-
ning time and solution quality into account.
Discussion of directions for further research in the areas of graph parti-
tioning and graph clustering.
The paper Benchmarks for Network Analysis, which was invited as a con-
tribution to the Encyclopedia of Social Network Analysis and Mining.
The primary location of information regarding the 10th DIMACS Implementation
Challenge is the website
Fortunato, Community detection in graphs, Physics Reports 486 (2010), no. 3–5,
E. Schaeffer, Graph clustering, Computer Science Review 1 (2007), no. 1, 27–64.
Schloegel, G. Karypis, and V. Kumar, Graph partitioning for high-performance scientific
simulations, Sourcebook of parallel computing (Jack Dongarra, Ian Foster, Geoffrey Fox, William
Gropp, Ken Kennedy, Linda Torczon, and Andy White, eds.) Morgan Kaufmann Publishers,
2003, pp. 491–541.
Previous Page Next Page