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

DOI10.1016/J.DAM.2015.10.001MaRDI QIDQ266828zbMATH OpenOpenAlexFDO

Authors Raed Jaberi

Publication date 7 April 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6000

zbMATH Keywords

approximation algorithmsgraph algorithms2-vertex-connected componentsstrong articulation points

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Abstract: 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(m{n}^2)$ time, the second in $O(nm)$ time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in $O(n{m}^2)$ 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^{3}m)$ time, and we show that the $k$-vertex-connected components ($k$-vccs) of a directed graph can be computed in $O(m{n}^{2k-3})$ 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.

Recommendations

• Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: an experimental study
• 2-vertex connectivity in directed graphs
• 2-vertex connectivity in directed graphs
• Computing the 2-blocks of directed graphs
• 2-Connectivity in Directed Graphs (Invited Talk)
• On finding the strongly connected components in a directed graph
• 2-connectivity in directed graphs: an experimental study
• 2-edge connectivity in directed graphs
• 2-Edge Connectivity in Directed Graphs
• On the complexity of strongly connected components in directed hypergraphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• 2-connectivity in directed graphs: an experimental study
• 2-vertex connectivity in directed graphs
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• An algorithm for finding all thek-components of a digraph
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Bijoin points, bibridges, and biblocks of directed graphs
• Computing the 2-blocks of directed graphs
• Depth-First Search and Linear Graph Algorithms
• Dominators in Linear Time
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Finding strong bridges and strong articulation points in linear time
• Introduction to algorithms.
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
• The tree Constraint
• Using expander graphs to find vertex connectivity
• k-Blocks and Ultrablocks in Graphs

Cited in

(10)

• Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: an experimental study
• Computing 2-twinless blocks
• 2-Connectivity in Directed Graphs (Invited Talk)
• 2-edge-twinless blocks
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• On the complexity of strongly connected components in directed hypergraphs
• 2-vertex connectivity in directed graphs
• Dynamic Dominators and Low-High Orders in DAGs
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• 2-vertex connectivity in directed graphs

This page was built for publication: On computing the 2-vertex-connected components of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266828)