Date of Award
Tsin, Yung (School of Computer Science)
CC BY-NC-ND 4.0
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).
Moazzami, Katayoon, "A Distributed Algorithm for Finding Separation Pairs in a Computer Network" (2009). Electronic Theses and Dissertations. 330.