COMPUTING THE 2-BLOCKS OF DIRECTED GRAPHS

作     者：Jaberi, Raed 

作者机构：Tech Univ Ilmenau Fac Comp Sci & Automat D-98693 Ilmenau Germany 

出 版 物：《RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS》 (法国自动化、信息与运筹学；理论与应用信息)

年 卷 期：2015年第49卷第2期

页      面：93-119页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Directed graphs strong articulation points strong bridges 2-blocks graph algorithms approximation algorithms 

摘      要：Let G be a directed graph. A 2-directed block in G is a maximal vertex set C-2d subset of V with vertical bar C-2d vertical bar = 2 such that for each pair of distinct vertices x, y is an element of C-2d, there exist two vertex-disjoint paths from x to y and two vertex-disjoint paths from y to x in G. In this paper we present two algorithms for computing the 2-directed blocks of G in O(min{m, (t(sap) + t(sb))n}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{m, t(sap)n}n) time and we show that the 2-edge blocks of G can be computed in O(min{m, t(sb)n}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), 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.