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

DOI10.1016/J.DAM.2021.08.026MaRDI QIDQ2235263OpenAlexFDO

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

zbMATH Keywords

graph algorithmreachabilitydirected graphstrong articulation pointstrong bridge

Mathematics Subject Classification ID

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

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

Cites work

• A linear-time algorithm for a special case of disjoint set union
• A note on finding the bridges of a graph
• Dominators in Linear Time
• Edge-disjoint spanning trees and depth-first search
• Finding strong bridges and strong articulation points in linear time
• Graph theory
• Introduction to algorithms.
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Maximal Flow Through a Network
• The algorithm design manual

Cited in

(5)

• Strong articulation points and strong bridges in large scale graphs
• Safety in \(s\)-\(t\) paths, trails and walks
• Finding strong bridges and strong articulation points in linear time
• 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)