A multilevel graph partitioner with edge sparsification achieves proven linear expected work and a 1.49x average speedup in KaMinPar with only about 1% average cut increase.
High-Quality Shared-Memory Graph Partitioning
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Linear-Time Multilevel Graph Partitioning via Edge Sparsification
A multilevel graph partitioner with edge sparsification achieves proven linear expected work and a 1.49x average speedup in KaMinPar with only about 1% average cut increase.