An Optimal Distributed Algorithm for Computing Bridge-Connected Components
P.P. Chaudhuri · The Computer Journal · 1997
In this paper I present a distributed algorithm that finds the bridge-connected components of a connected undirected graph. The algorithm uses O(n) messages and O(n) units of time, where n is the number of nodes in the graph. It is shown that the algorithm is optimal in communication complexity to within a constant factor.