# 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

 Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI) Publikationstyp Hochschulschrift Publikationsjahr 2019 Sprache Englisch Identifikator KITopen-ID: 1000098895 Verlag Karlsruhe 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 Referent/Betreuer Prof. P. Sanders Schlagwörter graph algorithms, parallel algorithms, data structures, shared-memory algorithms
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page