Strong articulation points and strong bridges in large scale graphs

DOI10.1007/s00453-015-9991-zzbMath1333.05289OpenAlexW2023856768WikidataQ61609291 ScholiaQ61609291MaRDI QIDQ270023

Giuseppe F. Italiano, Luigi Laura, Federico Santaroni, Donatella Firmani, Loukas Georgiadis

Publication date: 6 April 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-9991-z

zbMATH Keywords

graph algorithmsgraph connectivitystrong articulation pointslarge scale graphsstrong bridges

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

Computing 2-twinless blocks

Uses Software

• SNAP
• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding strong bridges and strong articulation points in linear time
• 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
• Dominators, Directed Bipolar Orders, and Independent Spanning Trees
• Applications of Path Compression on Balanced Trees
• 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
• A fast algorithm for finding dominators in a flowgraph
• Efficiency of a Good But Not Linear Set Union Algorithm
• On Finding Lowest Common Ancestors in Trees
• Dominators in Linear Time
• Finding Dominators in Practice
• The tree Constraint
• Depth-First Search and Linear Graph Algorithms