Date of Award

2009

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Tsin, Yung (School of Computer Science)

Keywords

Computer Science.

Rights

CC BY-NC-ND 4.0

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).

Share

COinS