Date of Award

2013

Publication Type

Master 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

info:eu-repo/semantics/openAccess

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

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