Name
Abstract | ||
|---|---|---|
The graph partitioning problem is widely used and studied in many practical and theoretical applications. Today, multilevel strategies represent one of the most effective and efficient generic frameworks for solving this problem on large-scale graphs. Most of the attention in designing multilevel partitioning frameworks has been on the refinement phase. In this work, we focus on the coarsening phase, which is responsible for creating structures similar to the original but smaller graphs. We compare different matching- and AMG-based coarsening schemes, experiment with the algebraic distance between nodes, and demonstrate computational results on several classes of graphs that emphasize the running time and quality advantages of different coarsening schemes. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2670338 | ACM Journal of Experimental Algorithmics |
Keywords | DocType | Volume |
multilevel strategy,algorithms,different coarsenings,computational result,advanced coarsening scheme,coarsening,multilevel algorithm,different matching,refinement phase,multilevel partitioning framework,efficient generic framework,amg-based coarsening scheme,optimization,uncoarsening,algebraic distance,refinement,graph theory,graph partitioning,numerical algorithms and problems,coarsening phase,computational optimization | Conference | 19, |
Issue | Citations | PageRank |
1 | 26 | 0.83 |
References | Authors | |
25 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilya Safro | 1 | 226 | 25.29 |
| peter sanders | 2 | 361 | 29.35 |
| Christian Schulz | 3 | 240 | 24.10 |