News=> Graph Partitioning and Graph Clustering

The Tenth DIMACS Implementation Challenge:  Graph Partitioning and Graph Clustering
 http://www.cc.gatech.edu/dimacs10/
 
The Implementation Challenge starts in February 2011 with the collection of testbeds. Participants are invited to carry out research projects related to the problem area and to present research papers at the Challenge's workshop to be held in Atlanta (Georgia, USA)on February 13/14, 2012. Refereed workshop proceedings willbe published in the AMS-DIMACS book series.
 
Motivation:
Graph partitioning and graph clustering are ubiquitous subtasks in many application areas. Generally speaking, both techniques 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: What are the communities within an (online) social network? How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer? How must components be organized on a computer chip such that they can communicate efficiently with each other? What are the segments of a digital image? Which functions are
certain genes (most likely) responsible for?
 
Goals:
The goals of the Implementation Challenge are (i) to determine how algorithms depend on the structure of the underlying data sets, (ii) to determine realistic algorithm performance, and (iii) to obtain a reproducible picture of the state-of-the-art in the area of graph partitioning and graph clustering algorithms. To this end we are identifying a standard set of benchmark instances and generators. Based on our initial proposals and
after a discussion with the community, we would like to establish the most appropriate problem formulations and objective functions for different applications.