KaHIP

KaHIP - Karlsruhe High Quality Partitioning - is a family of graph partitioning programs. It includes KaFFPa (Karlsruhe Fast Flow Partitioner), which is a multilevel graph partitioning algorithm, in its variants Strong, Eco and Fast, KaFFPaE (KaFFPaEvolutionary) which is a parallel evolutionary algorithm that uses KaFFPa to provide combine and mutation operations, as well as KaBaPE which extends the evolutionary algorithm. Moreover, specialized techniques are included to partition road networks (Buffoon), to output a vertex separator from a given partition or techniques geared towards efficient partitioning of social networks.


References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Baum, Moritz; Dibbelt, Julian; Pajor, Thomas; Sauer, Jonas; Wagner, Dorothea; Zündorf, Tobias: Energy-optimal routes for battery electric vehicles (2020)
  2. Recalde, Diego; Torres, Ramiro; Vaca, Polo: An exact approach for the multi-constraint graph partitioning problem (2020)
  3. Kara, Gökçehan; Özturan, Can: Algorithm 1002: Graph coloring based parallel push-relabel algorithm for the maximum flow problem (2019)
  4. Biedermann, Sonja; Henzinger, Monika; Schulz, Christian; Schuster, Bernhard: Memetic graph clustering (2018)
  5. Henzinger, Alexandra; Noe, Alexander; Schulz, Christian: ILP-based local search for graph partitioning (2018)
  6. Christian Schulz, Jesper Larsson Traeff: VieM v1.00 -- Vienna Mapping and Sparse Quadratic Assignment User Guide (2017) arXiv
  7. Meyerhenke, Henning; Sanders, Peter; Schulz, Christian: Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering (2016)
  8. Delling, Daniel; Fleischman, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F.: An exact combinatorial algorithm for minimum graph bisection (2015)
  9. Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Christian Schulz: k-way Hypergraph Partitioning via n-Level Recursive Bisection (2015) arXiv
  10. Younes, Ahmed: A bounded-error quantum polynomial-time algorithm for two graph bisection problems (2015)
  11. Duan, Ran; Pettie, Seth: Linear-time approximation for maximum weight matching (2014)
  12. Safro, Ilya; Sanders, Peter; Schulz, Christian: Advanced coarsening schemes for graph partitioning (2014)
  13. Sanders, Peter; Schulz, Christian: Distributed evolutionary graph partitioning (2012)