10th DIMACS Implementation Challenge - Graph Partitioning and Graph Clustering

February 13 - 14, 2012
Klaus Advanced Computing Building
Georgia Institute of Technology
Atlanta, Georgia

Organizers:

David A. Bader, Georgia Institute of Technology, USA

Henning Meyerhenke, Karlsruhe Institute of Technology, Germany

Peter Sanders, Karlsruhe Institute of Technology, Germany

Dorothea Wagner, Karlsruhe Institute of Technology, Germany

Workshop Program:

Monday, February 13, 2012

 8:30 -  9:15  Breakfast

 8:45 -  9:15  Registration

 9:15 -  9:30  Welcome

 9:30 - 10:45  Session 1: Graph Partitioning

               High Quality Graph Partitioning
               Peter Sanders and Christian Schulz, Karlsruhe Institute of Technology, Germany

               Graph Partitioning with Natural Cuts
               Daniel Delling, Microsoft Research Silicon Valley, USA 

               Exact Combinatorial Branch-and-Bound for Graph Bisection
               Daniel Delling, Microsoft Research Silicon Valley, USA 

10:45 - 11:15  Coffee break

11:15 - 12:30  Session 2: Graph Partitioning and Related

               Graph Partitioning for Scalable Distributed Graph Computations
               Aydin Buluc, Lawrence Berkeley National Laboratory, and Kamesh Madduri, The Pennsylvania State University

               Shape Optimizing Load Balancing for Parallel Adaptive Numerical Simulations Using MPI
               Henning Meyerhenke, Karlsruhe Institute of Technology, Germany

               Scalable and Accurate Algorithm for Graph Clustering
               Hristo N. Djidjev, Los Alamos National Labratory, and Melih Onus, Cankaya University, Turkey

12:30 -  2:00  Lunch break

 2:00 -  3:15  Session 3: Hypergraph Partitioning

               Abusing a hypergraph partitioner for unweighted graph partitioning
               B. O. Fagginger Auer and R. H. Bisseling, Utrecht University, Netherlands

               An Evaluation of the Zoltan Parallel Graph and Hypergraph Partitioners
               Sivasankaran Rajamanickam and Erik G. Boman, Sandia National Laboratories, USA

               UMPa: A Multi-objective, multi-level partitioner for communication minimization
               Ümit V. Çatalyürek, Mehmet Deveci, Kamer Kaya, Ohio State University and Bora Uçar, LIP, ENS Lyon, France

 3:15 -  3:45  Coffee break

 3:45 -  5:00  Session 4: Modularity Clustering (I)

               A Divisive clustering technique for maximizing the modularity
               Ümit V. Çatalyürek, Kamer Kaya, The Ohio State University, and Johannes Langguth and Bora Uçar, LIP, ENS Lyon, France

               Modularity Maximization in Networks by Variable Neighborhood Search
               Daniel Aloise, Universidade Federal do Rio Grande do Norte, Brazil

               Community Detection by Modularity Maximization using GRASP with Path Relinking
               Mariá C. V. Nascimento, Universidade Federal de Sao Paulo, Brazil and
               Leonidas S. Pitsoulis, Aristotle University of Thessaloniki, Thessaloniki, Greece

 5:00 -  5:10  Break

 5:00 -  6:00  Session 5: Modularity Clustering (II)

               Using Stable Communities for Maximizing Modularity
               S. Srinivasan and S. Bhowmick, University of Nebraska at Omaha, USA

               Complete Hierarchical Community Clustering: A Case Study on Expansion and Modularity
               Michael Hamann, Tanja Hartmann and Dorothea Wagner, Karlsruhe Institute of Technology, Germany

Tuesday, February 14, 2012

 8:30 -  9:00  Breakfast
 
 9:00 -  9:30  Keynote: DIMACS Implementation Challenges: Past, Present, and Future
               David S. Johnson, AT&T Labs - Research

 9:30 - 10:20  Session 6: Parallel Modularity Clustering

               Parallel Community Detection for Massive Graphs
               E. Jason Riedy, David Ediger, David A. Bader, Georgia Institute of Technology, and Henning Meyerhenke, Georgia
               Institute of Technology, and Karlsruhe Institute of Technology, Germany

               Graph Coarsening and Clustering on the GPU
               B. O. Fagginger Auer and R. H. Bisseling, Utrecht University, Netherlands

10:20 - 10:45  Coffee break

10:45 - 12:00  Session 7: Clustering

               Experiments on Density-Constrained Graph Clustering
               Robert Gorke, Andrea Schumm, and Dorothea Wagner, Karlsruhe Institute of Technology, Germany

               An Ensemble Learning Strategy for Graph Clustering
               Michael Ovelgonne and Andreas Geyer-Schulz, Karlsruhe Institute of Technology, Germany

               Network Clustering via Clique Relaxations: A Community Based Approach
               Anurag Verma, Sergiy Butenko, Texas A&M University, USA

12:00 - 12:15  Break - Grab and Go lunch 

12:15 -  1:00  Challenge Results

 1:00 -  1:15  Summary

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage