Paper Info
Title
High Quality Graph Partitioning
Abstract
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 and 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.
Year
DOI
Venue
2012
10.1090/conm/588/11700
GRAPH PARTITIONING AND GRAPH CLUSTERING
DocType
Volume
ISSN
Conference
588
0271-4132
Citations 
PageRank 
References 
11
0.58
59
Authors
2
Name
Order
Citations
PageRank
Peter Sanders11957120.14
Christian Schulz224024.10