High Quality Graph Partitioning

The thesis presents recent work on balanced graph partitioning - partition the nodes of a graph into k blocks such that all blocks have about equal size and such that the number of cut edges is small. We report a number of advances on the classical multilevel approach. Moreover, we present a distributed evolutionary algorithm as well as novel techniques to guarantee the balance constraint. Overall this leads to a system that for many common benchmarks leads to both the best quality solution known and favorable tradeoffs between running time and solution quality.