An O(n(2)) self-stabilizing algorithm for computing bridge-connected components
This paper presents a self-stabilizing algorithm that finds the bridge-connected components of a connected undirected graph on an asynchronous distributed or network model of computation. An edge of a graph is a bridge if its removal disconnects the graph. The bridge-connected components problem consists of finding the maximal connected subgraphs (components) of the given graph such that none of the components contains a bridge. The output of the algorithm is available in a distributed manner in the sense that, upon termination of the algorithm, each node of the graph knows its component number: the component number is a representative node number which uniquely identifies a bridge-connected component. It has been proved that the algorithm is correct and requires O(n(2)) time if the depth-first search spanning tree of the graph is known, or else it requites O(n(2) + n . d . Delta) time, where n is the number of nodes, d is the graph diameter, and a is an upper bound on the degree of a node.
self-stabilizing algorithm bridge-connected components graphs distributed system time complexity