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
|
Betreuer | Diekert, Prof. Volker; Weiß, Dr. Armin |
Eingabedatum | 26. Februar 2020 |
---|