Staff:Prof. Dr. Peter Sanders, Karlsruher Institut für Technologie Prof. Dr. Dorothea Wagner, Karlsruher Institut für Technologie Dr. Christian Schulz, Uni Wien |
 |
|
 |
The primary goal of the project is to tackle general graph partitioning problems on large graphs and their applications. Balanced graph partitioning for total cut minimization is only the tip of the iceberg of many related problems that have been less intensively studied but overall have at least an equally wide range of applications. While we expect many of the approaches from the basic problem to help with the more general ones, many new questions and difficulties arise.
A good example for this is the generalization to hypergraphs where edges can connect more than two nodes. The basic approaches may transfer but we get at least two different objective functions and without further ideas, performance will drop dramatically because we get a term in the execution time that is the sum of the squares of the hyperedge sizes. Further examplary important generalizations are allowing multiple objectives, and looking at dynamic situations where the graph
changes over time. On the other hand, it is also important to look at specializations to families of graphs with particular properties that allow us to compute better solutions more efficiently. Lastly, we want to push the envelope with respect to
parallelization ranging from shared memory algorithms that better exploit the available hardware to the largest supercomputers where we also need to copartition the input graph and the interconnection network. The project will provide the most successful implementations as easy-to-use open source software.