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

DOI10.1016/j.dam.2015.10.001zbMath1333.05136arXiv1401.6000OpenAlexW2216685023MaRDI QIDQ266828

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

graph algorithmsapproximation algorithms2-vertex-connected componentsstrong articulation points

Mathematics Subject Classification ID

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

Related Items

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