Finding strong bridges and strong articulation points in linear time
From MaRDI portal
Publication:443716
DOI10.1016/j.tcs.2011.11.011zbMath1245.05128WikidataQ61609439 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
Related Items
Computing Critical Nodes in Directed Graphs, Unnamed Item, Minimum 2-vertex strongly biconnected spanning directed subgraph problem, Strong Connectivity in Directed Graphs under Failures, with Applications, Dynamic Dominators and Low-High Orders in DAGs, Computing the 2-blocks of directed graphs, Computing 2-twinless blocks, Unnamed Item, Model and methods to address urban road network problems with disruptions, The strong network orientation problem, On 2-strong connectivity orientations of mixed graphs and related problems, On computing the 2-vertex-connected components of directed graphs, Strong articulation points and strong bridges in large scale graphs, Finding dominators via disjoint set union, 2-vertex connectivity in directed graphs, Sparse certificates for 2-connectivity in directed graphs, Safety in \(s\)-\(t\) paths, trails and walks, A simplified algorithm computing all \(s-t\) bridges and articulation points, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph, 2-edge-twinless blocks, Directing Road Networks by Listing Strong Orientations, 2-Vertex Connectivity in 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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