A self-stabilizing algorithm for 3-edge-connectivity.
Date of Award
2006
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Computer Science.
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
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.
Recommended Citation
Saifullah, Abu Sayeed., "A self-stabilizing algorithm for 3-edge-connectivity." (2006). Electronic Theses and Dissertations. 742.
https://scholar.uwindsor.ca/etd/742