Date of Award
2013
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Applied sciences, Graph connectivity, Hopcroft and tarjan (1973), Triconnectivty, Tsin(2012)
Supervisor
Tsin, Yung H.
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
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.
Recommended Citation
Jiang, Zhigang, "An empirical study of 3-vertex connectivity algorithms" (2013). Electronic Theses and Dissertations. 4980.
https://scholar.uwindsor.ca/etd/4980