Distributed algorithm for finding the bridges of an undirected graph
Pranay Chaudhuri · International Journal of Electronics · 1993
A distributed algorithm is presented for finding the bridges of an undirected graph on a network model of computation. The output of the algorithm, i.e. the set of edges each of which is a bridge, is available in a distributed manner. More precisely, every node returns a set of nodes (may be empty) each of which together with that node forms a bridge of the given graph. For algorithms in such a computational model, two types of complexity measures are important. One is the time complexity, and the other is the message of communication complexity. These two complexities of the proposed algorithm are found to be O(d) and O(e), respectively, where d is the diameter and e is the number of edges of the graph.