KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering Multilevel Graph Partitioning Algorithms

Sanders, Peter ORCID iD icon 1; Schulz, Christian 1
1 Karlsruher Institut für Technologie (KIT)


We present a multi-level graph partitioning algorithm using novel local improvement algorithms and global search strategies transferred from multigrid linear solvers. Local improvement algorithms are based on max-flow min-cut computations and more localized FM searches. By combining these techniques, we obtain an algorithm that is fast on the one hand and on the other hand is able to improve the best known partitioning results for many inputs. For example, in Walshaw’s well known benchmark tables we achieve 317 improvements for the tables at 1%, 3% and 5% imbalance. Moreover, in 118 out of the 295 remaining cases we have been able to reproduce the best cut in this benchmark.

DOI: 10.1007/978-3-642-23719-5_40
Zitationen: 121
Zitationen: 111
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Buchaufsatz
Publikationsjahr 2011
Sprache Englisch
Identifikator ISBN: 978-3-642-23719-5
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097645
Erschienen in Algorithms – ESA 2011. 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings. Ed.: C. Demetrescu
Verlag Springer Verlag
Seiten 469–480
Serie Lecture Notes in Computer Science ; 6942
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page