KIT | KIT-Bibliothek | Impressum | Datenschutz

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.


Volltext §
DOI: 10.5445/IR/1000044868
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2014
Sprache Englisch
Identifikator urn:nbn:de:swb:90-448683
KITopen-ID: 1000044868
Verlag Karlsruher Institut für Technologie (KIT)
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdaten 13.06.2014
Referent/Betreuer Wagner, D.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page