KIT | KIT-Bibliothek | Impressum | Datenschutz

Advanced Coarsening Schemes for Graph Partitioning

Safro, Ilya; Sanders, Peter; Schulz, Christian

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

Open Access Logo


Download
Originalveröffentlichung
DOI: 10.1007/978-3-642-30850-5_32
Scopus
Zitationen: 10
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 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, Berlin
Seiten 369–380
Serie Lecture Notes in Computer Science ; 7276
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page