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

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 |

Jahr |
2019 |

Sprache |
Englisch |

Identifikator |
KITopen-ID: 1000098895 |

Verlag |
Karlsruhe |

Umfang |
XIII, 225 S. |

Abschlussart |
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 |

Schlagworte |
graph algorithms, parallel algorithms, data structures, shared-memory algorithms |

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft

KITopen Landing Page