KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering Graph Partitioning Algorithms

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


The paper gives an overview of our recent work on balanced graph partitioning – partition the nodes of a graph into k blocks such that all blocks have approximately equal size and such that the number of cut edges is small. This problem has numerous applications for example in parallel processing. We report on a scalable parallelization and a number of improvements on the classical multi-level approach which leads to improved partitioning quality. This includes an integration of flow methods, improved local search, several improved coarsening schemes, repeated runs similar to the approaches used in multigrid solvers, and an integration into a distributed evolutionary algorithm. Overall this leads to a system that for many common benchmarks leads to both the best quality solution known and favorable tradeoffs between running time and solution quality.

DOI: 10.1007/978-3-642-30850-5_3
Zitationen: 5
Zitationen: 5
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: 1000097639
Erschienen in Experimental Algorithms. Ed.: R. Klasing
Verlag Springer Verlag
Seiten 18–26
Serie Lecture Notes in Computer Science ; 7276
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page