zbMATH — the first resource for mathematics

High quality graph partitioning. (English) Zbl 1269.68115
Bader, David A. (ed.) et al., Graph partitioning and graph clustering. Proceedings of the 10th DIMACS implementation challenge workshop, Atlanta, GA, USA, February 13–14, 2012. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-9038-7/pbk; 978-0-8218-9869-7/ebook). Contemporary Mathematics 588, 1-17 (2013).
Summary: 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.
For the entire collection see [Zbl 1262.05001].

68W40 Analysis of algorithms
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
90C27 Combinatorial optimization
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)