A SILENT SELF-STABILIZING ALGORITHM FOR FINDING CUT-NODES AND BRIDGES
- 1 March 2005
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters
- Vol. 15 (01n02) , 183-198
Abstract
In this paper, we present a self-stabilizing algorithm for finding cut-nodes and bridges in arbitrary rooted networks with a low memory requirement (O( log (n)) bits per processor where n is the number of processors). Our algorithm is silent and must be composed with a silent self-stabilizing algorithm computing a Depth-First Search (DFS) Spanning Tree of the network. So, in the paper, we will prove that the composition of our algorithm with any silent self-stabilizing DFS algorithm is self-stabilizing. Finally, we will show that our algorithm needs O(n2) moves to reach a terminal configuration once the DFS spanning tree is computed. Note that this time complexity is equivalent to the best proposed solutions.Keywords
This publication has 12 references indexed in Scilit:
- A note on self-stabilizing articulation point detectionJournal of Systems Architecture, 1999
- A self-stabilizing algorithm for bridge findingDistributed Computing, 1999
- A SELF-STABILIZING ALGORITHM FOR FINDING ARTICULATION POINTSInternational Journal of Foundations of Computer Science, 1999
- An $O(n^2)$ Self-Stabilizing Algorithm for Computing Bridge-Connected ComponentsComputing, 1999
- Uniform dynamic self-stabilizing leader electionIEEE Transactions on Parallel and Distributed Systems, 1997
- Distributed Algorithms1994
- Self-stabilization of dynamic systems assuming only read/write atomicityDistributed Computing, 1993
- Optimal parallel algorithms for finding cut vertices and bridges of interval graphsInformation Processing Letters, 1992
- Efficient distributed algorithms solving problems about the connectivity of networkSystems and Computers in Japan, 1991
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974