An <i>O(n<SUP>2</SUP>)</i> self-stabilizing algorithm for computing bridge-connected components

作     者：Chaudhuri, P 

作者机构：Kuwait Univ Dept Elect & Comp Engn Safat Kuwait 

出 版 物：《COMPUTING》 (计算)

年 卷 期：1999年第62卷第1期

页      面：55-67页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：distributed system self-stabilizing algorithm graphs bridge-connected components time complexity 

摘      要：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.