KIT | KIT-Bibliothek | Impressum | Datenschutz

High-Performance Graph Algorithms

Looz, Moritz von

Abstract (englisch):

Ever since Euler took a stroll across the bridges of a city then called Königsberg, relationships of entities have been modeled as graphs. Being a useful abstraction when the structure of relationships is the significant aspect of a problem, popular uses of graphs include the modeling of social networks, supply chain dependencies, the internet, customer preferences, street networks or the who-eats-whom (aka food network) in an ecosystem.

In parallel computing, the assignment of sub-tasks to processes can massively influence the performance, since data dependencies between processes are significantly more expensive than within them. This scenario has been profitably modeled as a graph problem, with sub-tasks as vertices and their communication dependencies as edges.

Many graphs are governed by an underlying geometry. Some are derived directly from a geometric object, such as street networks or meshes from spatial simulations. Others have a hidden geometry, in which no explicit geometry information is known, but the graph structure follows an underlying geometry. A suitable embedding into this geometry would then show a close relationship between graph distances and geometric distances.
... mehr


Volltext §
DOI: 10.5445/IR/1000095908
Veröffentlicht am 19.06.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: 1000095908
Verlag Karlsruher Institut für Technologie (KIT)
Umfang XII, 129 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 23.01.2019
Projektinformation WAVE-Sim - TP ITI (BMBF, 01IH15004B)
SPP 1736 (DFG, DFG KOORD, ME 3619/3-2)
Bemerkung zur Veröffentlichung Der vollständige Name des Autors lautet: Moritz Graf von Looz-Corswarem
Schlagwörter graph partitioning, graph generation, hyperbolic random graphs, load balancing, parallel algorithms, distributed algorithms, k-means, geometric graph algorithms
Relationen in KITopen
Referent/Betreuer Meyerhenke, H.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page