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

Given a directed graph G and a pair of nodes s and t, an s-t bridge of G is an edge whose removal breaks all s-t paths of G. Similarly, an s-t articulation point of G is a node whose removal breaks all s-t paths of G. Computing the sequence of all s-t bridges of G (as well as the s-t articulation points) is a basic graph problem, solvable in linear time using the classical min-cut algorithm (Ford and Fulkerson, 1956).We show a simplified and self-contained algorithm computing all s-t bridges and s-t articulation points of G, based on a single graph traversal from s to t avoiding an arbitrary s-t path, which is interrupted at the s-t bridges. Its proof of correctness uses simple inductive arguments, making the problem an application of merely graph traversal, rather than of the more complex maximum flow problem. (C) 2021 The Author(s). Published by Elsevier B.V.