Previous Issues
Volume :29 Issue : 2 2002
Add To Cart
Download
A dynamic optimal stabilizing algorithm for finding stronglyconnected components
Auther : MEHMET HAKAN KARAATA AND FAWAZ AL-ANZ1
Department of Computer Engineering, Kuwait University,
P.O.Box 5969 Safat-13060 Kuwait. E-mail: karaata@ eng.kuniv.edu.kw, alanzi@eng.kuniv.edu.kw
ABSTRACT
An optimal self-stabilizing algorithm is presented that finds the strongly connected components of a directed graph on an underlying network after 0(C) rounds, where C is the length of the longest cycle in the graph. Because the algorithm is self-stabilizing, it is resilient to transient faults and does not require initialization. The proposed algorithm can withstand topology changes in the form of addition or removal of edges and vertices. A correctness proof of the algorithm is provided.
Keywords: Directed graphs; distributed systems; self-stabilization; strongly
connected components.