Finding strong bridges and strong articulation points in linear time

DOI10.1016/J.TCS.2011.11.011MaRDI QIDQ443716zbMATH OpenOpenAlexWikidataFDO

Authors Giuseppe F. Italiano, Luigi Laura, Federico Santaroni

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 articulation pointsstrong bridgesstrong connectivity

Mathematics Subject Classification ID

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

Recommendations

• Finding strong bridges and strong articulation points in linear time
• Strong articulation points and strong bridges in large scale graphs
• A simplified algorithm computing all \(s\)-\(t\) bridges and articulation points
• Strong connectivity in directed graphs under failures, with applications
• 2-Connectivity in Directed Graphs (Invited Talk)

Cites work

• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 1775413 (Why is no real title available?)
• scientific article; zbMATH DE number 3340124 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• A matroid approach to finding edge connectivity and packing arborescences
• Bijoin points, bibridges, and biblocks of directed graphs
• Depth-First Search and Linear Graph Algorithms
• Edge-disjoint spanning trees and depth-first search
• Efficient determination of the transitive closure of a directed graph
• Finding strong bridges and strong articulation points in linear time
• Introduction to algorithms.
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Matrices, Digraphs, and Determinants
• On computing a conditional edge-connectivity of a graph
• Restricted arc-connectivity of digraphs
• Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
• The Transitive Reduction of a Directed Graph
• The tree Constraint

Cited in

(27)

• scientific article; zbMATH DE number 7765396 (Why is no real title available?)
• Finding dominators via disjoint set union
• On computing the 2-vertex-connected components of directed graphs
• Strong articulation points and strong bridges in large scale graphs
• Computing the 2-blocks of directed graphs
• Safety in \(s\)-\(t\) paths, trails and walks
• Minimum 2-vertex strongly biconnected spanning directed subgraph problem
• Recognizing planar Laman graphs
• 2-vertex connectivity in directed graphs
• 2-vertex connectivity in directed graphs
• Finding strong bridges and strong articulation points in linear time
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Model and methods to address urban road network problems with disruptions
• Finding articulation points of large graphs in linear time
• 2-edge-twinless blocks
• The strong network orientation problem
• Sparse certificates for 2-connectivity in directed graphs
• Computing 2-twinless blocks
• Strong connectivity in directed graphs under failures, with applications
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
• scientific article; zbMATH DE number 3858437 (Why is no real title available?)
• Directing Road Networks by Listing Strong Orientations
• On 2-strong connectivity orientations of mixed graphs and related problems
• A simplified algorithm computing all \(s\)-\(t\) bridges and articulation points
• Computing Critical Nodes in Directed Graphs
• Dynamic Dominators and Low-High Orders in DAGs

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

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