A novel coarsening scheme for multilevel graph partitiong

When applying multilevel scheme to solve the static graph partitioning problem, shortcomings and limitations exist in the state-of-the-art coarsening schemes depend mainly on finding maximal matchings to obtain the successively coarse graphs, especially for partitioning irregular graphs, which can cause the multilevel algorithms to produce poor-quality solutions. This paper proposes an improved coarsening scheme by re-collapsing the matching in each coarsening step. The new coarsening scheme is more effective in quality, which is proved to be effective by both theoretical analysis and experimental results.