To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
This collection is related to the Workshop of the 10th DIMACS Implementation Challenge, which took place in Atlanta, Georgia (USA) on February 13-14, 2012. The purpose of DIMACS Implementation Challenges is to assess the practical performance of algorithms in a respective problem domain. These challenges are scientific competitions in area 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 between 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 transfer within the research areas of algorithms, data structures, and implementation techniques as well as a transfer back to the original applications.
The 10th challenge considered the two related problems of partitioning and clustering graphs. Both are ubiquitous subtasks in many application areas. Generally 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 algorithms are:
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 different algorithms and implementations were tested against the benchmark instances. Thereby future researchers are enabled to identify techniques that are most effective for a respective partitioning or clustering problemby using our benchmark set and by comparing their results to the challenge results.
PDF for Full front and end matter.
Preface David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner vii High Quality Graph Partitioning Peter Sanders and Christian Schulz 1 Abusing a Hypergraph Partitioner for Unweighted Graph Partitioning B.O. Fagginger Auer and R.H. Bisseling 19 Parallel Partitioning with Zoltan: Is Hypergraph Partitioning Worth It? Sivasankaran Rajamanickam and Erik G. Boman 37 UMPa: A Multi-objective, multi-level partitioner for communication minimization Umit V. Catalyurek, Mehmet Deveci, Kamer Kaya, and Bora Ucar 53 Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations Henning Meyerhenke 67 Graph Partitioning for Scalable Distributed Graph Computations Aydin Buluc and Kamesh Madduri 83 Using Graph Partitioning for Efficient Network Modularity Optimization Hristo Djidjev and Melih Onus 103 Modularity Maximization in Networks by Variable Neighborhood Search Daniel Aloise, Gilles Caporossi, Pierre Hansen, Leo Liberti, Sylvain Perron, and Manuel Ruiz 113 Network Clustering via Clique Relaxations: A Community Based Approach Anurag Verma and Sergiy Butenko 129 Identifying Base Clusters and Their Application to Maximizing Modularity Sriram Srinivasan, Tanmoy Chakraborty, and Sanjukta Bhowmick 141 Complete Hierarchical Cut-Clustering: A Case Study on Expansion and Modularity Michael Hamann, Tanja Hartmann, and Dorothea Wagner 157 A Partitioning-Based Divisive Clustering Technique for Maximizing the Modularity Umit V. Catalyurek, Kamer Kaya, Johannes Langguth, and Bora Ucar 171 An Ensemble Learning Strategy for Graph Clustering Michael Ovelgonne and Andreas Geyer-Schulz 187 Parallel Community Detection for Massive Graphs E. Jason Riedy, Henning Meyerhenke, David Ediger, and David A. Bader 207 Graph Coarsening and Clustering on the GPU B.O. Fagginger Auer and R.H. Bisseling 223