×

KaHyPar

swMATH ID: 20718
Software Authors: Sebastian Schlag, Peter Sanders, Tobias Heuer
Description: 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.
Homepage: https://github.com/SebastianSchlag/kahypar
Source Code:  https://github.com/SebastianSchlag/kahypar
Keywords: multilevel hypergraph partitioning; algorithm engineering; fm local search; partitioning algorithms; Hypergraph partitioning; HGP
Related Software: Zoltan; SparseMatrix; PaToH; DIMACS; UMPa; KaFFPa; Trilinos; GitHub; Julia; AMPL; StochasticPrograms.jl; GLPK; MathOptInterface.jl; PowerModels.jl; DISROPT; EAGO.jl; Modelica; HYPE; HyperX; Gravity
Cited in: 10 Publications

Citations by Year