Finding strong bridges and strong articulation points in linear time
From MaRDI portal
Publication:443716
DOI10.1016/J.TCS.2011.11.011zbMATH Open1245.05128OpenAlexW2011379509WikidataQ61609439 ScholiaQ61609439MaRDI QIDQ443716FDOQ443716
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
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
- Introduction to algorithms.
- Depth-First Search and Linear Graph Algorithms
- Efficient determination of the transitive closure of a directed graph
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- 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
- A linear-time algorithm for a special case of disjoint set union
- Edge-disjoint spanning trees and depth-first search
- Restricted arc-connectivity of digraphs
- Title not available (Why is that?)
- On computing a conditional edge-connectivity of a graph
- A matroid approach to finding edge connectivity and packing arborescences
- Title not available (Why is that?)
- Matrices, Digraphs, and Determinants
- Finding strong bridges and strong articulation points in linear time
- Title not available (Why is that?)
Cited In (27)
- Finding dominators via disjoint set union
- On computing the 2-vertex-connected components of directed graphs
- Computing the 2-blocks of directed graphs
- Strong articulation points and strong bridges in large scale 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
- Computing 2-twinless blocks
- Sparse certificates for 2-connectivity in directed graphs
- Strong connectivity in directed graphs under failures, with applications
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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)
