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.

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

Romeo Rizzi;Elia C. Zirondelli
2021

Abstract

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.
Reachability
Graph algorithm
Strong bridge
Strong articulation point
Directed graph
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/1054198
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact