Date of Award
2009
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Computer Science.
Supervisor
Tsin, Yung (School of 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
One of the main problems in graph theory is graph connectivity which is often studied for network reliability problems.It can be studied from two aspects, vertex-connectivity and edge-connectivity. Vertex connectivity is the smallest number of vertices whose deletion will cause a connected graph to be disconnected. We focus our work on finding separation pairs of a graph which is the set of pairs of vertices that deleting them would disconnect a graph. Finding separation pairs can be used in solving vertex-connectivity problem and finding the triconnected components of the graph. The algorithms presented during the past are non-linear or if linear, very complicated. This work is based on Tarjan and Hopcroft's paper which uses Depth-First Search and finds the separation pairs in linear time. Our goal is to present an algorithm that finds the separation pairs in an asynchronous distributed computer network using distributed Depth-First search (DDFS).
Recommended Citation
Moazzami, Katayoon, "A Distributed Algorithm for Finding Separation Pairs in a Computer Network" (2009). Electronic Theses and Dissertations. 330.
https://scholar.uwindsor.ca/etd/330