KIT | KIT-Bibliothek | Impressum | Datenschutz

Deep multilevel graph partitioning

Gottesbüren, Lars; Heuer, Tobias ORCID iD icon; Sanders, Peter ORCID iD icon; Schulz, Christian; Seemaier, Daniel


Partitioning a graph into blocks of "roughly equal" weight while cutting only few edges is a fundamental problem in computer science with a wide range of applications. In particular, the problem is a building block in applications that require parallel processing. While the amount of available cores in parallel architectures has significantly increased in recent years, state-of-the-art graph partitioning algorithms do not work well if the input needs to be partitioned into a large number of blocks. Often currently available algorithms compute highly imbalanced solutions, solutions of low quality, or have excessive running time for this case. This is due to the fact that most high-quality general-purpose graph partitioners are multilevel algorithms which perform graph coarsening to build a hierarchy of graphs, initial partitioning to compute an initial solution, and local improvement to improve the solution throughout the hierarchy. However, for large number of blocks, the smallest graph in the hierarchy that is used for initial partitioning still has to be large.
In this work, we substantially mitigate these problems by introducing deep multilevel graph partitioning and a shared-memory implementation thereof. ... mehr

Verlagsausgabe §
DOI: 10.5445/IR/1000138388
Veröffentlicht am 04.10.2021
DOI: 10.4230/LIPIcs.ESA.2021.48
Zitationen: 10
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-9597720-4-4
ISSN: 1868-8969
KITopen-ID: 1000138388
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 29th Annual European Symposium on Algorithms (ESA 2021): 6-8 September 2021, online. Ed.: P. Mutzel
Veranstaltung 29th Annual European Symposium on Algorithms (ESA 2021), Online, 06.09.2021 – 08.09.2021
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 48
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 204
Schlagwörter graph partitioning, graph algorithms, multilevel, shared-memory, parallel
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page