DISTRIBUTED ALGORITHM FOR FINDING THE BRIDGES OF AN UNDIRECTED GRAPH

A distributed algorithm is presented for finding the bridges of an und irected graph on a network model of computation. The output of the alg orithm, 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 n odes (may be empty) each of which together with that node forms a brid ge of the given graph. For algorithms in such a computational model, t wo types of complexity measures are important. One is the time complex ity, and the other is the message of communication complexity. These t wo complexities of the proposed algorithm are found to be 0(d) and O(e ), respectively, where d is the diameter and e is the number of edges of the graph.