A SILENT SELF-STABILIZING ALGORITHM FOR FINDING CUT-NODES AND BRIDGES
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.
References
- Communications of the Association of the Computing Machinery 17, 643 (1974). Crossref, ISI, Google Scholar
- Communications of the ACM 37, 468 (1971). Google Scholar
- SIAM J. Computing 1(2), (1972). Google Scholar
- M. Ahuja and Y. Zhu. An efficient distributed algorithm for finding articulation points, bridges and biconnected components in asynchronous networks. In 9th Conference on Foundations of Software Technology and Theorical Computer Science, Banglore, India, pages 99-108. LNCS 405, 1989 . Google Scholar
- Systems and Computers in Japan 22, 1 (1991). Crossref, Google Scholar
- Information Processing Letters 42, 229 (1992). Crossref, ISI, Google Scholar
- International Journal of Foundations of Computer Science 10(1), 33 (1999). Link, ISI, Google Scholar
- Distributed Computing 12(1), 47 (1999). Crossref, ISI, Google Scholar
- Computing 62, 55 (1999). Crossref, ISI, Google Scholar
- Journal of Systems Architecture 45(14), 1249 (1999). Crossref, ISI, Google Scholar
- Distributed Computing 7, 3 (1993). Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 8(4), 424 (1997). Crossref, ISI, Google Scholar
-
G. Tel , Introduction to distributed algorithms ( Cambridge University Press , 1994 ) . Crossref, Google Scholar - T. Herman. Adaptivity through distributed convergence. PhD thesis, University of Texas at Austin, Departement of Computer Science, 1991 . Google Scholar
- Information Processing Letters 49(6), 297 (1994). Crossref, ISI, Google Scholar
- Chicago Journal of Theoretical Computer Science (1998). Google Scholar
- Distributed Computing 14(3), 147 (2001). Crossref, ISI, Google Scholar


