Finding strong bridges and strong articulation points in linear time

DOI10.1016/j.tcs.2011.11.011zbMath1245.05128OpenAlexW2011379509WikidataQ61609439 ScholiaQ61609439MaRDI QIDQ443716

Giuseppe F. Italiano, Federico Santaroni, Luigi Laura

Publication date: 13 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.11.011

zbMATH Keywords

graph algorithmsstrong connectivitystrong articulation pointsstrong bridges

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (24)

On computing the 2-vertex-connected components of directed graphs ⋮ Strong articulation points and strong bridges in large scale graphs ⋮ 2-Vertex Connectivity in Directed Graphs ⋮ Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time ⋮ Minimum 2-vertex strongly biconnected spanning directed subgraph problem ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ 2-vertex connectivity in directed graphs ⋮ Computing Critical Nodes in Directed Graphs ⋮ 2-edge-twinless blocks ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Finding dominators via disjoint set union ⋮ Model and methods to address urban road network problems with disruptions ⋮ The strong network orientation problem ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ Unnamed Item ⋮ A simplified algorithm computing all \(s-t\) bridges and articulation points ⋮ Unnamed Item ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Directing Road Networks by Listing Strong Orientations ⋮ Computing the 2-blocks of directed graphs ⋮ Computing 2-twinless blocks ⋮ Safety in \(s\)-\(t\) paths, trails and walks

Cites Work

• A linear-time algorithm for a special case of disjoint set union
• On computing a conditional edge-connectivity of a graph
• Edge-disjoint spanning trees and depth-first search
• A matroid approach to finding edge connectivity and packing arborescences
• Restricted arc-connectivity of digraphs
• Efficient determination of the transitive closure of a directed graph
• Finding Strong Bridges and Strong Articulation Points in Linear Time
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Matrices, Digraphs, and Determinants
• Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs
• Bijoin points, bibridges, and biblocks of directed graphs
• The tree Constraint
• The Transitive Reduction of a Directed Graph
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding strong bridges and strong articulation points in linear time