A self-stabilizing algorithm for bridge finding |
| |
Authors: | Mehmet Hakan Karaata Pranay Chaudhuri |
| |
Affiliation: | (1) Department of Electrical and Computer Engineering, Kuwait University, P.O. Box 5969 Safat-13060 Kuwait, (e-mail: {karaata, pranay}@eng.kuniv.edu.kw) , KW |
| |
Abstract: | Summary. A self-stabilizing algorithm is presented in this paper that finds the bridges of a connected undirected graph on a distributed or network model of computation after moves. The algorithm is resilient to transient faults and does not require initialization. In addition, a correctness proof of the algorithm is provided. The paper concludes with remarks on the time complexity of the algorithm. Received: July 1997 / Accepted: January 1999 |
| |
Keywords: | :Biconnected components – Bridge – Distributed systems – Self-stabilization |
本文献已被 SpringerLink 等数据库收录! |