2-Vertex Connectivity in Directed Graphs

DOI10.1007/978-3-662-47672-7_49zbMath1395.68208OpenAlexW2287845547WikidataQ61609301 ScholiaQ61609301MaRDI QIDQ3448819

Loukas Georgiadis, Nikos Parotsidis, Luigi Laura, Giuseppe F. Italiano

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_49

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

On computing the 2-vertex-connected components of directed graphs, Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time, Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs, 2-edge-twinless blocks, Sparse certificates for 2-connectivity in directed graphs, Dynamic Dominators and Low-High Orders in DAGs, Computing the 2-blocks of directed graphs, Computing 2-twinless blocks

Cites Work

• On computing the 2-vertex-connected components of directed graphs
• Finding strong bridges and strong articulation points in linear time
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
• Finding Dominators in Directed Graphs
• Dominators in Linear Time
• Dominator Tree Certification and Divergent Spanning Trees
• 2-Edge Connectivity in Directed Graphs
• Computing the 2-blocks of directed graphs
• Depth-First Search and Linear Graph Algorithms