Date of Award

2013

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Tsin, Yung H.

Keywords

Applied sciences, Graph connectivity, Hopcroft and tarjan (1973), Triconnectivty, Tsin(2012)

Rights

CC BY-NC-ND 4.0

Abstract

Graph connectivity is one of the most basic properties of graph. Owing to this reason, it is fundamental to the studies of many important applications such as network reliability, cluster analysis, graph optimization, quantum physics, bioinformatics and social networks. Triconnectivity is a topic in graph connectivity which has been used in graph drawing, graph decomposition in geometry constraint solver, and social network studies. Hopcroft and Tarjan (1973) proposed the first linear-time algorithm for this problem. Although elegant, this algorithm is very complex and contains many minor but crucial errors which make it very difficult to understand and implement correctly. Gutwenger and Mutzel (2001) published a list of errors, outlining how to fix them and implemented the corrected algorithm.Recently, Tsin (2012) proposed a new linear-time algorithm which is based on a new graph transformation technique. Tsin's algorithm is conceptually very simple and performs one less pass over the given graph than Hopcroft et al. These make the algorithm much easier to implement. In this thesis , we implemented Tsin's algorithm and compare its performance with Gutwenger and Mutzel's implementation of the algorithm of Hopcroft and Tarjan by carrying out an empirical study.

Share

COinS