An efficient distributed algorithm for 3-edge-connectivity
A distributed algorithm for finding the cut-edges and the 3-edge-connected components of an asynchronous computer network is presented. For a network with n nodes and m links, the algorithm has worst-case O(n + h(T)(2)) time and O(m + nh(T)) message complexity, where h(T) < n. The algorithm is message optimal when h(T) is an element of O(m/n) which includes dense networks (i.e. m is an element of theta(n(2))). The previously best known distributed algorithm has a worst-case O(n(3)) time and message complexity.
distributed algorithms 3-edge-connected component analysis of algorithms graph connectivity cut-pair network reliability