On computing the 2-vertex-connected components of directed graphs

Original · EN

In this paper we consider the problem of computing the 2-vertex-connected components (2-vccs) of directed graphs. We present two new algorithms for solving this problem. The first algorithm runs in O(mn²) time, the second in O(nm) time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in O(nm²) time. In this paper, we investigate the relationship between 2-vccs and dominator trees. We also present an algorithm for computing the 3-vertex-connected components (3-vccs) of a directed graph in O(n³m) time, and we show that the k-vertex-connected components (k-vccs) of a directed graph can be computed in O(mn²ᵏ⁻³) time. Finally, we consider three applications of our new algorithms, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest 2-vertex-connected spanning subgraph of 2-vertex-connected directed graph.