A simplified algorithm computing all [formula omitted]-[formula omitted] 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. [ABSTRACT FROM AUTHOR]