KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
DOI: 10.5445/IR/1000035713

High Quality Graph Partitioning

Schulz, Christian

The thesis presents recent work on balanced graph partitioning - partition the nodes of a graph into k blocks such that all blocks have about equal size and such that the number of cut edges is small. We report a number of advances on the classical multilevel approach. Moreover, we present a distributed evolutionary algorithm as well as novel techniques to guarantee the balance constraint. 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.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2013
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-357133
KITopen-ID: 1000035713
Verlag Karlsruhe
Abschlussart Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdaten 05.07.2013
Referent/Betreuer Prof. P. Sanders
Schlagworte Graph Partitioning, Optimization, Distributed Computation, Algorithms
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page