2014/07/23 by Raed Jaberi, Jaberi, Raed
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1407.6178
arxiv created 2014/07/23 · arxiv updated 2014/07/24
Let G be a directed graph. A 2-directed block in G is a maximal vertex set C2d⊆ V with |C2d|≥ 2 such that for each pair of distinct vertices x,y ∈ C2d, there exist two vertex-disjoint paths from x to y and two vertex-disjoint paths from y to x in G. In contrast to the 2-vertex-connected components of G, the subgraphs induced by the 2-directed blocks may consist of few or no edges. In this paper we present two algorithms for computing the 2-directed blocks of G in O(min\lbrace m,(tsap+tsb)n\rbrace n) time, where tsap is the number of the strong articulation points of G and tsb is the number of the 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,tsap n\rbrace n) time and we show that the 2-edge blocks of G can be computed in O(min \lbrace m, tsb n \rbrace n) time. In this paper 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), find a minimum cardinality set E*⊆ E such that G*=(V,E*) is strongly connected and the strong articulation points of G coincide with the strong articulation points of G*. This problem is called minimum strongly connected spanning subgraph with the same strong articulation points. 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.