KaHyPar - Karlsruhe Hypergraph Partitioning. KaHyPar is a multilevel hypergraph partitioning framework for optimizing the cut- and the (λ − 1)-metric. It supports both recursive bisection and direct k-way partitioning. As a multilevel algorithm, it consist of three phases: In the coarsening phase, the hypergraph is coarsened to obtain a hierarchy of smaller hypergraphs. After applying an initial partitioning algorithm to the smallest hypergraph in the second phase, coarsening is undone and, at each level, a local search method is used to improve the partition induced by the coarser level. KaHyPar instantiates the multilevel approach in its most extreme version, removing only a single vertex in every level of the hierarchy. By using this very fine grained n-level approach combined with strong local search heuristics, it computes solutions of very high quality. Its algorithms and detailed experimental results are presented in several research publications.
Keywords for this software
References in zbMATH (referenced in 4 articles )
Showing results 1 to 4 of 4.
- Shaydulin, Ruslan; Chen, Jie; Safro, Ilya: Relaxation-based coarsening for multilevel hypergraph partitioning (2019)
- Akhremtsev, Yaroslav; Heuer, Tobias; Sanders, Peter; Schlag, Sebastian: Engineering a direct (k)-way hypergraph partitioning algorithm (2017)
- Schlag, Sebastian; Henne, Vitali; Heuer, Tobias; Meyerhenke, Henning; Sanders, Peter; Schulz, Christian: (k)-way hypergraph partitioning via (n)-level recursive bisection (2016)
- Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Christian Schulz: k-way Hypergraph Partitioning via n-Level Recursive Bisection (2015) arXiv