Bachelorarbeit BCLR-2020-02

Bibliograph.
Daten
Goletz, Sven: Berechnung von kanonischen s-t-MinCut Bäumen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 2 (2020).
51 Seiten, deutsch.
Kurzfassung

Die s-t-MinCuts aller Paare von Knoten s,t eines ungerichteten und gewichteten Graphen G können durch einen Strukturbaum B repräsentiert werden, der mindestens die Knoten des Graphen G enthält. Der Wert eines s-t-MinCuts ergibt sich dabei als Minimum der Kantengewichte des eindeutigen Weges in B, der s und t miteinander verbindet; der MinCut selbst ergibt sich dabei durch die beiden Zusammenhangskomponenten, in welche der Baum B bei Entfernen einer der Kanten dieses Weges, deren Kantengewicht dem MinCut-Wert entspricht, zerfällt.

Ein kanonischer Strukturbaum benötigt dabei höchstens n-2 zusätzliche Knoten, wobei n die Anzahl der Knoten im Graphen G ist. Besitzt der Graph G Gelenkpunkte oder Brücken, so bleiben diese im Strukturbaum erhalten. Die Konstruktion eines kanonischen Strukturbaums in Polynomialzeit kann nicht alle möglichen s-t-MinCuts berücksichtigen, da es exponentiell viele von ihnen geben kann. Stattdessen könnte man als Grundlage für einen Algorithmus lediglich die kleinsten s-t-MinCuts für jedes Paar von Knoten heranziehen, da es von diesen nur polynomiell viele gibt und diese in polynomieller Zeit berechnet werden können.

Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerDiekert, Prof. Volker; Weiß, Dr. Armin
Eingabedatum26. Februar 2020
   Publ. Informatik