This collection is related to the Workshop of the 10th DIMACS Implementa-
tion Challenge, which took place in Atlanta, Georgia (USA) on February 13-14,
2012. The purpose of DIMACS Implementation Challenges1 is to assess the prac-
tical performance of algorithms in a respective problem domain. These challenges
are scientific competitions in areas of interest where worst case and probabilistic
analysis yield unrealistic results. Where analysis fails, experimentation can provide
insights into realistic algorithm performance and thereby help to bridge the gap be-
tween theory and practice. For this purpose common benchmark instances, mostly
from real applications, are established. By evaluating different implementations on
these instances, the challenges create a reproducible picture of the state of the art
in the area under consideration. This helps to foster an effective technology trans-
fer within the research areas of algorithms, data structures, and implementation
techniques as well as a transfer back to the original applications.
The topics of the previous nine challenges are as follows (in chronological or-
der): Network Flows and Matching (1990-91), Maximum Clique, Graph Coloring
and Satisfiability (1992-93), Parallel Algorithms for Combinatorial Problems (1993-
94), Fragment Assembly and Genome Rearrangements (1994-95), Priority Queues,
Dictionaries, and Multi-Dimensional Point Sets (1995-96), Near Neighbor Searches
(1998-99), Semidefinite and Related Optimization Problems (1999-2000), The Trav-
eling Salesman Problem (2000-01), and Shortest Path Problems (2005-06).
1. Introducing the 10th Challenge –
Graph Partitioning and Graph Clustering
The 10th challenge considered the two related problems of partitioning and
clustering graphs. Both are ubiquitous subtasks in many application areas. Gen-
erally speaking, techniques for graph partitioning and graph clustering aim at the
identification of vertex subsets with many internal and few external edges. To
name only a few, problems addressed by graph partitioning and graph clustering
• What are the communities within an (online) social network?
• How do I speed up a numerical simulation by mapping it eﬃciently onto
a parallel computer?
• How must components be organized on a computer chip such that they
can communicate eﬃciently with each other?
• What are the segments of a digital image?
• Which functions are certain genes (most likely) responsible for?