Treffer: Algorithms for computing the 2-vertex-connected components and the 2-blocks of directed graphs ; Algorithmen zur Berechnung der 2-fach knotenzusammenhängenden Komponenten und 2-Blöcken in gerichteten Graphen

In dieser Dissertation beschäftigen wir uns mit mehreren Problemen in gerichteten Graphen. Zuerst betrachten wir das Problem der Berechnung der $2$-fach knotenzusammenhängenden Komponenten in gerichteten Graphen. Wir präsentieren einen neuen Algorithmus zur Lösung dieses Problems in Zeit $O(nm)$ und wir betrachten drei Anwendungen dieses Algorithmus. Sei $G=(V,E)$ ein gerichteter Graph. Ein $2$-gerichteter Block in $G$ ist eine maximale Knotenmenge $C^{2d}\subseteq V$ mit $|C^{2d}|\geq 2$, so dass für jedes Paar von verschiedenen Knoten $x,y\in C^{2d}$ zwei knoten disjunkte Wege von $x$ nach $y$ und zwei knoten disjunke Wege von $y$ nach $x$ in $G$ existieren.Wir präsentieren zwei Algorithmen zur Berechnung der $2$-gerichteten Blöcke von $G$ in Zeit $O(\min\lbrace m,(t_{sap}+t_{sb})n\rbrace n)$, wobei $t_{sap}$ die Anzahl der starken Artikulations\-punkte von $G$ und $t_{sb}$ die Anzahl der starken Brücken von $G$ ist. Wir untersuchen zwei weitere relevante Begriffe: die $2$-starken Blöcke und die $2$-Kanten-Blöcke von $G$.Wir geben zwei Algorithmen zur Berechnung der $2$-starken Blöcke von $G$in Zeit $O( \min \lbrace m,t_{sap} n\rbrace n)$ an und wir zeigen, dass die $2$-Kanten-Blöcke von $G$ in Zeit $O(\min \lbrace m, t_{sb} n \rbrace n)$ bestimmt werden können. Wir untersuchen auch einige Optimierungsprobleme, die mit starken Artikulationspunkten und $2$-Blöcken zusammenhängen. Gegeben sei ein stark zusammenhängender Graph $G=(V,E)$. Wir wollen einen minimalen stark zusammenhängenden spannenden Teilgraphen $G^{*}=(V,E^{*})$ von $G$ finden, so dass die starken Artikulationspunkte von $G$ mit den starken Artikulationspunkten von $G^{*}$ übereinstimmen. Wir zeigen, dass es einen $17/3$-Approximationsalgorithmus für dieses NP-schwere Problem gibt, der lineare Laufzeit hat. Wir betrachten auch das Problem der Berechnung eines minimalen stark zusammenhängenden span\-nenden Teilgraphen mit denselben $2$-Blöcken in einem stark zusammenhängenden Graphen. Wir präsentieren Approximationsalgorithmen für drei Versionen ...