A simplified algorithm computing all s-t bridges and articulation points

DOI10.1016/J.DAM.2021.08.026OpenAlexW3201233154MaRDI QIDQ2235263FDOQ2235263

Authors: Massimo Cairo, Shahbaz Khan, Romeo Rizzi, Alexandru I. Tomescu, Elia C. Zirondelli, Sebastian M. Schmidt 

Publication date: 21 October 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.08.026

Recommendations

• Finding strong bridges and strong articulation points in linear time
• Finding strong bridges and strong articulation points in linear time
• Safety in \(s\)-\(t\) paths, trails and walks
• Strong articulation points and strong bridges in large scale graphs
• scientific article; zbMATH DE number 3858437

zbMATH Keywords

graph algorithmreachabilitydirected graphstrong articulation pointstrong bridge

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites Work

• The algorithm design manual
• Maximal Flow Through a Network
• Graph theory
• Introduction to algorithms.
• A note on finding the bridges of a graph
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Dominators in Linear Time
• 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

Cited In (5)

• Finding strong bridges and strong articulation points in linear time
• Strong articulation points and strong bridges in large scale graphs
• Safety in \(s\)-\(t\) paths, trails and walks
• A simple systolic method to find all bridges of an undirected graph
• Finding strong bridges and strong articulation points in linear time

This page was built for publication: A simplified algorithm computing all \(s\)-\(t\) bridges and articulation points

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