4. CONTRIBUTIONS TO THIS COLLECTION xi
• results/: Partitions submitted as part of the challenge as well as code
for their evaluation and the resulting data
All respective files can be found and downloaded by following links from the home-
page. Researchers are particularly encouraged to download and use the graphs we
compiled and archived.
4. Contributions to this Collection
In this section we give a short overview of the papers that were selected for
this collection. All of them were presented at the Workshop of the 10th DIMACS
Implementation Challenge and contributed to the success of the event. Not all
solvers described in these papers actually entered the challenge. Also, not all solvers
that entered the challenge are part of this collection.
4.1. Graph Partitioning. The winner in terms of graph partitioning quality
was KaPa, by Sanders and Schulz, described in their paper High Quality Graph
Partitioning. KaPa combines the solutions of several related solvers developed by
the same authors. It is a set of algorithms which use a combination of strategies.
Among these strategies are network flows, evolutionary algorithms, edge ratings
for approximate maximum weighted matchings in the multilevel process, repeti-
tive improvement cycles, and problem-specific local search techniques based on the
Fiduccia-Mattheyses (FM) heuristic.
Abusing a Hypergraph Partitioner for Unweighted Graph Partitioning, by Fag-
ginger Auer and Bisseling, describes Mondriaan, a package for matrix and hyper-
graph partitioning, and its (ab)use for graph partitioning. While Mondriaan usually
computes worse edge cuts than state-of-the-art graph partitioners, the solutions are
In Parallel Partitioning with Zoltan: Is Hypergraph Partitioning Worth It?,
Rajamanickam and Boman describe a partitioner which is very powerful in that it
is designed for scalable parallelism on large asymmetric hypergraphs.
C ¸ataly¨ urek, Deveci, Kaya, and U¸ car present in UMPa: A Multi-objective,
multi-level partitioner a system doing recursive multi-objective hypergraph bipar-
titioning that takes the bottleneck communication volume as primary objective
function into account but also looks for solutions with small total communication.
The related task of repartitioning dynamic graphs is addressed by Meyerhenke
in Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simula-
tions. Diffusive methods are employed to determine both how many elements have
to migrate between processors as well as which elements are chosen for migration.
The properties of the diffusive processes usually lead to nicely shaped partitions.
In Graph Partitioning for Scalable Distributed Graph Computations, by Bu-
luc and Madduri, the authors develop a method for partitioning large-scale sparse
graphs with skewed degree distribution. The approach aims to partition the graph
into balanced parts with low edge cuts, a challenge for these types of graphs, so that
they can be used on distributed-memory systems where communication is often a
major bottleneck in running time. The authors derive upper bounds on the com-
munication costs incurred for a two-dimensional partitioning during breadth-first
search. The performance results using the large-scale DIMACS challenge graphs
shows that reducing work and communication imbalance among partitions is more
important than minimizing the total edge cut.