Distributed algorithms on edge connectivity problems
S.-N. Yang, Min Cheng · 2002
Connectivity of a network dictates the routability and survivability of a network. The paper investigates the edge connectivity problems in distributed environments. For a given network or graph G, one can distributively find bridges in the network first then find the 2-edge connected components. Both algorithms proposed, bridge finding and 2-edge connected component identifying, require only O(m) message complexity, where m is the number of edge in G. The paper also shows an efficient distributed 2-edge cutset algorithm that has O(n/sup 2/) message complexity, where n is the number of nodes in G.>