Invited Session Wed.2.H 3021

Wednesday, 13:15 - 14:45 h, Room: H 3021

Cluster 2: Combinatorial optimization [...]

Graph partitioning and clustering


Chair: Renato Werneck



Wednesday, 13:15 - 13:40 h, Room: H 3021, Talk 1

Renato Werneck
Exact combinatorial branch-and-bound for graph bisection

Coauthors: Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn


We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We present stronger lower bounds, improved branching rules, and a new decomposition technique that contracts entire regions of the graph without losing optimality guarantees. In practice, our algorithm works particularly well on instances with relatively small minimum bisections, solving large real-world graphs (with tens of thousands to millions of vertices) to optimality.



Wednesday, 13:45 - 14:10 h, Room: H 3021, Talk 2

Schulz Christian
High quality graph partitioning

Coauthors: Peter Sanders, Christian Schulz


We present an overview over our graph partitioners KaFFPa (Karlsruhe Fast Flow Partitioner) and KaFFPaE (KaFFPa Evolutionary). KaFFPa is a multilevel graph partitioning algorithm which on the one hand uses novel local improvement algorithms based on max-flow and min-cut computations and more localized FM searches and on the other hand uses more sophisticated global search strategies transferred from multi-grid linear solvers.
KaFFPaE is a distributed evolutionary algorithm to solve the Graph Partitioning Problem. KaFFPaE uses KaFFPa which provides new effective crossover and mutation operators. By combining these with a scalable communication protocol we obtain a system that is able to improve the best known partitioning results for many inputs.



Wednesday, 14:15 - 14:40 h, Room: H 3021, Talk 3

Henning Meyerhenke
Current trends in graph clustering

Coauthors: David A. Bader, Jason Riedy


Graph clustering has become very popular in recent years and is also known as community detection in networks. Generally speaking, graph clustering aims at the identification of vertex subsets with many internal and few external edges. The problem of finding clusters based on the objective function modularity was one category in the recently finished 10th DIMACS Implementation Challenge. We review successful techniques determined by the outcome of the challenge and describe our work on parallelization strategies.


  unsecured personal loans . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.