KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel and External High Quality Graph Partitioning

Akhremtsev, Yaroslav

Abstract:

Partitioning graphs into k blocks of roughly equal size such that few edges run between the blocks is a key tool for processing and analyzing large complex real-world networks. The graph partitioning problem has multiple practical applications in parallel and distributed computations, data storage, image processing, VLSI physical design and many more. Furthermore, recently, size, variety, and structural complexity of real-world networks has grown dramatically. Therefore, there is a demand for efficient graph partitioning algorithms that fully utilize computational power and memory capacity of modern machines.

A popular and successful heuristic to compute a high-quality partitions of large networks in reasonable time is $\textit{multi-level graph partitioning}$ approach which contracts the graph preserving its structure and then partitions it using a complex graph partitioning algorithm. Specifically, the multi-level graph partitioning approach consists of three main phases: coarsening, initial partitioning, and uncoarsening. During the coarsening phase, the graph is recursively contracted preserving its structure and properties until it is small enough to compute its initial partition during the initial partitioning phase. ... mehr


Volltext §
DOI: 10.5445/IR/1000098895
Veröffentlicht am 15.10.2019
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2019
Sprache Englisch
Identifikator KITopen-ID: 1000098895
Verlag Karlsruher Institut für Technologie (KIT)
Umfang XIII, 225 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 29.05.2019
Schlagwörter graph algorithms, parallel algorithms, data structures, shared-memory algorithms
Referent/Betreuer Sanders, P.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page