Parallel Processing Letters World Scientific Publishing Company A SILENT SELF-STABILIZING ALGORITHM FOR FINDING CUT-NODES AND BRIDGES

In this paper, we present a self-stabilizing algorithm for finding cut-nodes and bridges in arbitrary rooted networks with a low memory requirement ( ( ( )) bits per processor where is the number of processors). Our algorithm is silent and must be composed with a silent self-stabilizing algorithm computing a Depth-First Search ( ) Spanning Tree of the network. So, in the paper, we will prove that the composition of our algorithm with any silent self-stabilizing algorithm is self-stabilizing. Finally, we will show that our algorithm needs ( ) moves to reach a terminal configuration once the spanning tree is computed. Note that this time complexity is equivalent to the best proposed solutions