On computing the 2-vertex-connected components of directed graphs
From MaRDI portal
Publication:266828
DOI10.1016/j.dam.2015.10.001zbMath1333.05136arXiv1401.6000OpenAlexW2216685023MaRDI QIDQ266828
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
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Related Items (6)
2-Vertex Connectivity in Directed Graphs ⋮ Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time ⋮ 2-vertex connectivity in directed graphs ⋮ 2-edge-twinless blocks ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Computing 2-twinless blocks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding strong bridges and strong articulation points in linear time
- A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
- k-Blocks and Ultrablocks in Graphs
- Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- 2-Vertex Connectivity in Directed Graphs
- Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
- Using expander graphs to find vertex connectivity
- Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs
- An algorithm for finding all thek-components of a digraph
- Bijoin points, bibridges, and biblocks of directed graphs
- Dominators in Linear Time
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- 2-Connectivity in Directed Graphs: An Experimental Study
- The tree Constraint
- Computing the 2-blocks of directed graphs
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: On computing the 2-vertex-connected components of directed graphs
