Algorithms for computing the 2-vertex-connected components and the 2-blocks of directed graphs

Jaberi, Raed

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 dieses Problems, die sich in der Art der $2$-Blöcke unterscheiden. Im Gegensatz zu $2$-stark-zusammenhängenden Komponenten kann Entfernung der nicht zu $2$-gerichteten Blöcken gehörenden starken Artikulations\-punkte aus $G$ diese Blöcke ändern. Wir untersuchen das Problem der Berechnung einer minimalen Teilmenge $V^{*}$ der starken Artikulationspunkte, die nicht in diesen Blöcke liegen, so dass das Entfernen von $V^{*}$ denselben Effekt hat. Außerdem untersuchen wir andere Versionen dieses Problems, die sich in der Art der $2$-Blöcke unterscheiden. Ein gerichteter Graph $G=(V,E)$ heißt einfach zusammenhängend, wenn für jedes Paar von Knoten $v,w\in V$ höchstens ein einfacher Weg von $v$ nach $w$ in $G$ existiert. Buchsbaum und Carlisle (1993) gaben einen Algorithmus an, der in Zeit $O(n^{2})$ überprüft, ob $G$ einfach zusammenhängend ist. In dieser Dissertation beschreiben wir eine verbesserte Version dieses Algorithmus, die Laufzeit $O(s\cdot t+m)$ hat, wobei $s,t$ die Anzahl der Quellen beziehungsweise Senken im reduzierten Graphen sind, den man auf folgende Weise erhält: Kontrahieren jeder stark zusammenhängenden Komponente zu einem Knoten und dann Eliminierung von Knoten mit Eingangsgrad oder Ausgangsgrad $1$ durch eine Kontrahierenoperation. Außerdem zeigen wir, dass das Problem der Berechnung einer Kantenteilmenge $C\subseteq E$ (beziehungsweise Knotenteilmenge $F\subseteq V$), deren Löschen einen einfach-zusammenhängenden Graphen übrig lässt, NP-schwer ist.

In this dissertation we study several problems in directed graphs. First we consider the problem of computing the $2$-vertex-connected components of directed graphs. We present a new algorithm for solving this problem in $O(nm)$ time and we consider three applications of this algorithm. Let $G=(V,E)$ be a directed graph. A $2$-directed block in $G$ is a maximal vertex set $C^{2d}\subseteq V$ with $|C^{2d}|\geq 2$ such that for each pair of distinct vertices $x,y \in C^{2d}$ there exist two vertex-disjoint paths from $x$ to $y$ and two vertex-disjoint paths from $y$ to $x$ in $G$. We present two algorithms for computing the $2$-directed blocks of $G$ in $O(\min\lbrace m,(t_{sap}+t_{sb})n\rbrace n)$ time, where $t_{sap}$ is the number of strong articulation points of $G$ and $t_{sb}$ is the number of strong bridges of $G$. Furthermore, we study two related concepts: the $2$-strong blocks and the $2$-edge blocks of $G$.We give two algorithms for computing the $2$-strong blocks of $G$ in $O( \min \lbrace m,t_{sap} n\rbrace n)$ time and we show that the $2$-edge blocks of $G$ can be computed in $O(\min \lbrace m, t_{sb} n \rbrace n)$ time. We also study some optimization problems related to the strong articulation points and the $2$-blocks of a directed graph. Given a strongly connected graph $G=(V,E)$, we want to find a minimum strongly connected spanning subgraph $G^{*}=(V,E^{*})$ of $G$ such that the strong articulation points of $G$ coincide with the strong articulation points of $G^{*}$. We show that there is a linear time $17/3$-approximation algorithm for this NP-hard problem. We also consider the problem of finding a minimum strongly connected spanning subgraph with the same $2$-blocks in a strongly connected graph $G$. We present approximation algorithms for three versions of this problem, depending on the type of $2$-blocks. Unlike $2$-vertex-connected components, removing the strong articulation points of $G$ that do not belong to the $2$-directed blocks of $G$ may change these blocks. We study the problem of finding a minimum cardinality subset $V^{*}$ of strong articulation points that are not in these blocks such that the removal of $V^{*}$ has the same effect. Moreover, we study other versions of this problem depending on the type of $2$-blocks. A directed graph $G=(V,E)$ is called singly-connected if for each pair of vertices $v,w \in V$ there is at most one simple path from $v$ to $w$ in $G$. Buchsbaum and Carlisle (1993) gave an algorithm for testing whether $G$ is singly-connected in $O(n^{2})$ time. Here we describe a refined version of this algorithm with running time $O(s\cdot t+m)$, where $s$ and $t$ are the number of sources and sinks, respectively, in the reduced graph $G^{r}$ obtained by first contracting each strongly connected component of $G$ into one vertex and then eliminating vertices of indegree or outdegree $1$ by a contraction operation. Moreover, we show that the problem of finding a minimum cardinality edge subset $C\subseteq E$ (respectively, vertex subset $F\subseteq V$) whose removal from $G$ leaves a singly-connected graph is NP-hard.

Zitieren

Zitierform:

Jaberi, Raed: Algorithms for computing the 2-vertex-connected components and the 2-blocks of directed graphs. 2015.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export