KaHIP - Karlsruhe High Quality Partitioning - is a family of graph partitioning programs that tackle the balanced graph partitioning problem. It focuses on solution quality and implements flow-based methods, more-localized local searches, and several parallel and sequential meta-heuristics.
|Tags||C++ Library Scientific Computing Scientific software Graph partitioning|
|Operating Systems||Linux (32/64 bit) Mac OS|
Release Notes: This release adds huge max-flow min-cut instances, created with the partitioning framework and containing up to 2.6 billion edges. The max-flow min-cut instances stem from the local search algorithms within KaFFPa that are used to improve a bipartition of the graph.
Release Notes: This version integrates the size-constrained label propagation clustering algorithm as a standalone program.
Release Notes: This is a major update improving partitioning speed and solution quality on social networks and Web graphs. It achieves this by integrating novel coarsening schemes that can also be used as simple local search algorithms. For example, this version can partition a Web graph with half a billion edges in roughly one minute while cutting far fewer edges than Metis.
Release Notes: This is the initial release.