KIT | KIT-Bibliothek | Impressum | Datenschutz

Advanced Coarsening Schemes for Graph Partitioning

Safro, Ilya; Sanders, Peter 1; Schulz, Christian 1
1 Karlsruher Institut für Technologie (KIT)


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 structurally 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 coarsenings.

DOI: 10.1007/978-3-642-30850-5_32
Zitationen: 15
Zitationen: 16
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2012
Sprache Englisch
Identifikator ISBN: 978-3-642-30850-5
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097642
Erschienen in Experimental Algorithms. Ed.: R. Klasing
Verlag Springer Verlag
Seiten 369–380
Serie Lecture Notes in Computer Science ; 7276
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page