Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
From MaRDI portal
Abstract: We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a -way partition. The framework generalizes the flow-based improvement algorithm of KaFFPa from graphs to hypergraphs and is integrated into the hypergraph partitioner KaHyPar. By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas while still having a running time comparable to that of hMetis.
Recommendations
- Multilevel Acyclic Hypergraph Partitioning
- Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
- Multilevel Hypergraph Partitioning with Vertex Weights Revisited
- Parallel multilevel algorithms for hypergraph partitioning
- Relaxation-based coarsening for multilevel hypergraph partitioning
- Method of partition of networks with fixed degrees of nodes and network flows
- Aggregative coarsening for multilevel hypergraph partitioning
- \(n\)-level graph partitioning
- Using graph partitioning for efficient network modularity optimization
Cites work
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 49142 (Why is no real title available?)
- A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
- A new approach to the maximum-flow problem
- An Efficient Heuristic Procedure for Partitioning Graphs
- An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
- Cutsets and partitions of hypergraphs
- Encapsulating Multiple Communication-Cost Metrics in Partitioning Sparse Rectangular Matrices for Parallel Matrix-Vector Multiplies
- Engineering a direct \(k\)-way hypergraph partitioning algorithm
- Engineering multilevel graph partitioning algorithms
- Handbook of Approximation Algorithms and Metaheuristics
- Improving coarsening schemes for hypergraph partitioning by exploiting community structure
- Maximal Flow Through a Network
- Maximum flows by incremental breadth-first search
- Modeling hypergraphs by graphs with the same mincut properties
- Multi-level direct \(K\)-way hypergraph partitioning with multiple constraints and fixed vertices
- Multiple-way network partitioning
- On the structure of all minimum cuts in a network and applications
- Parallel multilevel algorithms for hypergraph partitioning
- Recent directions in netlist partitioning: a survey
- The University of Florida sparse matrix collection
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- k-way hypergraph partitioning via n-level recursive bisection
Cited in
(8)- Performance-driven layer assignment by integer linear programming and path-constrained hypergraph partitioning
- Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
- Improving coarsening schemes for hypergraph partitioning by exploiting community structure
- scientific article; zbMATH DE number 176474 (Why is no real title available?)
- k-way hypergraph partitioning via n-level recursive bisection
- Engineering a direct \(k\)-way hypergraph partitioning algorithm
- Hypergraph Cuts with General Splitting Functions
- Aggregative coarsening for multilevel hypergraph partitioning
This page was built for publication: Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140705)
