KIT | KIT-Bibliothek | Impressum | Datenschutz

Geometric Inhomogeneous Random Graphs for Algorithm Engineering

Weyand, Christopher ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

The design and analysis of graph algorithms is heavily based on the worst case.
In practice, however, many algorithms perform much better than the worst case would suggest.
Furthermore, various problems can be tackled more efficiently if one assumes the input to be, in a sense, realistic.
The field of network science, which studies the structure and emergence of real-world networks, identifies locality and heterogeneity as two frequently occurring properties.

A popular model that captures these properties are geometric inhomogeneous random graphs (GIRGs), which is a generalization of hyperbolic random graphs (HRGs).
Aside from their importance to network science, GIRGs can be an immensely valuable tool in algorithm engineering.
Since they convincingly mimic real-world networks, guarantees about quality and performance of an algorithm on instances of the model can be transferred to real-world applications.
They have model parameters to control the amount of heterogeneity and locality, which allows to evaluate those properties in isolation while keeping the rest fixed.
Moreover, they can be efficiently generated which allows for experimental analysis.
... mehr


Volltext §
DOI: 10.5445/IR/1000158520
Veröffentlicht am 09.05.2023
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsdatum 09.05.2023
Sprache Englisch
Identifikator KITopen-ID: 1000158520
Verlag Karlsruher Institut für Technologie (KIT)
Umfang 144 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 21.04.2023
Referent/Betreuer Bläsius, Thomas
Meyer, Ulrich
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page