------------------------------------------------------------
We are pleased to announce the release of 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 consists
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.
KaHyPar contains fast coarsening schemes that incorporate global information about the community structure
into the coarsening process. It uses a portfolio-based approach to initial partitioning and employs highly
engineered refinement algorithms (including max-flow computations) for both bipartitioning and direct k-way
partitioning that are specifically tailored to the n-level approach. Additional features include a memetic algorithm,
partitioning with variable block weights, and partitioning with fixed vertices.
The software is released under the GPL 3.0 license.
Website: http://www.kahypar.org
We are glad for any comments, pull requests, and error reports (or even bug fixes) that you send us.
--
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics - Algorithms II
Sebastian Schlag, M.Sc.
Doctoral Researcher
Am Fasanengarten 5, Gebäude 50.34
76131 Karlsruhe, Germany
Phone: +49 721 608-45270
Fax: +49 721 608-43088
Email: sebastian.schlag@kit.edu<mailto:sebastian.schlag@kit.edu>
Web: http://www.kit.edu/
KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association ?
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
