(Apologies for cross-posting)
The Tenth DIMACS Implementation Challenge:
Graph Partitioning and Graph Clustering
http://www.cc.gatech.edu/dimacs10/
=== Call for Participation ===
*********************************************************************
On behalf of the Center for Discrete Mathematics and Theoretical
Computer Science DIMACS, the organizing committee invites
participation in an Implementation Challenge focusing on Graph
Partitioning and Graph Clustering. 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 will
be 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.
Testbed:
We invite researchers from various application areas to provide
interesting data sets for graph partitioning and graph clustering
problems. Contributions could consist either of sample data sets
from a true application or of realistic instance generators
resembling practical data sets. Also, we invite the specification
of interesting objective functions based on real-world
applications. Our goal is to construct a modern library of test
problems reflecting current input sizes. The library will be
available for study both during and after the Challenge.
Developing Graph Partitioning and Graph Clustering Algorithms:
Algorithms may be developed for one or more categories (graph
partitioning / graph clustering, each with different objectives)
of the Challenge. Projects may involve either public domain or
proprietary codes. More details on the structure of the Challenge
will be announced later, please refer to the Challenge website
above.
How to Participate:
All information on the Challenge is available on the Challenge
website above. To register for the Challenge, please send an
email to dimacs-challenge-orga (at) cc.gatech.edu and register to the
participants' mailing list dimacs-challenge-10 (at) cc.gatech.edu.
Note that neither DIMACS nor the committee members can provide
financial support for research projects or machine cycles for the
experiments.
Committees:
The organizing committee consists of the coordinators David A.
Bader (Georgia Institute of Technology), Peter Sanders (Karlsruhe
Institute of Technology) and Dorothea Wagner (Karlsruhe Institute
of Technology), assisted by Henning Meyerhenke (Georgia Institute
of Technology). The advisory board members are Bruce Hendrickson
(Sandia National Laboratories), David S. Johnson (AT&T Labs -
Research), and Chris Walshaw (University of Greenwich).
*********************************************************************
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
