An empirical study of 3-vertex connectivity algorithms.
详细信息
文摘
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.