KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Volltext
URN: urn:nbn:de:swb:90-448683

Algorithms for Graph Connectivity and Cut Problems - Connectivity Augmentation, All-Pairs Minimum Cut, and Cut-Based Clustering

Hartmann, Tanja

Abstract:
We address a collection of related connectivity and cut problems in simple graphs that reach from the augmentation of planar graphs to be k-regular and c-connected to new data structures representing minimum separating cuts and algorithms that smoothly maintain Gomory-Hu trees in evolving graphs, and finally to an analysis of the cut-based clustering approach of Flake et al. and its adaption to dynamic scenarios.


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2014
Sprache Englisch
Identifikator KITopen-ID: 1000044868
Verlag Karlsruhe
Abschlussart Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdaten 13.06.2014
Referent/Betreuer Prof. D. Wagner
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page