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