Engineering multilevel graph partitioning algorithms
From MaRDI portal
Abstract: We present a multi-level graph partitioning algorithm using novel local improvement algorithms and global search strategies transferred from the multi-grid community. Local improvement algorithms are based max-flow min-cut computations and more localized FM searches. By combining these techniques, we obtain an algorithm that is fast on the one hand and on the other hand is able to improve the best known partitioning results for many inputs. For example, in Walshaw's well known benchmark tables we achieve 317 improvements for the tables 1%, 3% and 5% imbalance. Moreover, in 118 additional cases we have been able to reproduce the best cut in this benchmark.
Recommendations
Cited in
(39)- SOFSEM 2005: Theory and Practice of Computer Science
- Algorithm 1003: Mongoose, a graph coarsening and partitioning library
- A multilevel tabu search algorithm for balanced partitioning of unstructured grids
- Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
- Algorithm Engineering for Optimal Graph Bipartization
- Candidate sets for alternative routes in road networks
- Perfect reconstruction two-channel filter banks on arbitrary graphs
- A partitioning requiring rapidity and quality: the multilevel method and partitions refinement algorithms
- Relaxation-based coarsening for multilevel hypergraph partitioning
- Leveraging special-purpose hardware for local search heuristics
- A two-level graph partitioning problem arising in mobile wireless communications
- A new method, the fusion fission, for the relaxed \(k\)-way graph partitioning problem, and comparisons with some multilevel algorithms
- Scalable high-quality hypergraph partitioning
- Finding near-optimal weight independent sets at scale
- Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
- \(n\)-level graph partitioning
- Column-generation based bounds for the homogeneous areas problem
- Multilevel iterated tabu search for the multi-constraint graph partitioning problem
- Employee workload balancing by graph partitioning
- Better Process Mapping and Sparse Quadratic Assignment
- Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
- Jet: multilevel graph partitioning on graphics processing units
- Experimental and Efficient Algorithms
- scientific article; zbMATH DE number 4106284 (Why is no real title available?)
- Multilevel algorithms for acyclic partitioning of directed acyclic graphs
- Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
- Multilevel graph partitioning for three-dimensional discrete fracture network flow simulations
- Efficient implementation of a synchronous parallel push-relabel algorithm
- scientific article; zbMATH DE number 7286677 (Why is no real title available?)
- Optimizing warehouse product allocation at JD.com: a community detection-driven approach
- Quality matching and local improvement for multilevel graph-partitioning
- The parallel finite element system M++ with integrated multilevel preconditioning and multilevel Monte Carlo methods
- A reactive self-tuning scheme for multilevel graph partitioning
- High quality graph partitioning
- Fission: Practical algorithms for computing minimum balanced node separators
- ILP-Based Local Search for Graph Partitioning
- Advanced coarsening schemes for graph partitioning
- An algorithm for improving graph partitions
- Parallel unconstrained local search for partitioning irregular graphs
This page was built for publication: Engineering multilevel graph partitioning algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3092253)
