A self-stabilizing algorithm for 3-edge-connectivity.
Date of Award
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.
The notion of self-stabilization was first proposed by Dijkstra [37, 38].A system is self-stabilizing if, starting at any state, possibly illegitimate, it eventually converges to a legitimate state in finite time. In this thesis, we are proposing a self-stabilizing algorithm for 3-edge-connectivity of an asynchronous distributed model of computation. This is the first ever self-stabilizing algorithm in the literature for detecting the 3-edge-connected components. It is applicable on a depth-first tree of the network. The result is kept in a distributed fashion in the sense that, upon stabilization of the system, each processor knows all other processors that are 3-edge-connected to it. Assuming that the depth-first search algorithm has stabilized, the system with n processors requires O( n2) moves to determine all the 3-edge-connected components in a way such that, for each component, the information is available at one processor only. Stabilization of this phase is followed by another phase of O(n2) moves which, in the legitimate state, lets all other processors detect their respective components. (Abstract shortened by UMI.)Dept. of Computer Science. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2006 .S25. Source: Masters Abstracts International, Volume: 45-01, page: 0364. Thesis (M.Sc.)--University of Windsor (Canada), 2006.
Saifullah, Abu Sayeed., "A self-stabilizing algorithm for 3-edge-connectivity." (2006). Electronic Theses and Dissertations. 742.