A study of three-edge connectivity algorithms - Refinement and implementation

There are quite a number of linear algorithms to compute 3-edge connected components of a multi-graph. In this thesis, we study the three most efficient algorithms and exclude other algorithms that are obviously inferior as they use different types of transformation in multiple phases. We present a data structure model for cut-pair deletion in order to save space and to be able to handle larger input sizes on a platform. Using complexity arguments we also present a modification to one of the three algorithms that does not look for cut-pairs. We then show through our experimental results that this algorithm and another one that does not distinguish between cut-pairs have the fastest execution time, and each of them is better than the other for some cases. To the best of our knowledge, till now, there is no such an effort to show how the performance of the algorithms varies as the type and the size of given graph changes. Correctness proofs of the proposed way for cut-pair deletion and the modification are presented as well.

Name thesis:degree_name

M.Sc.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Windsor

Year dc:date.issued

2007

Author dc:creator

• Norouzi, Nima

Contributors dc:contributor

• scholarship@uwindsor.ca

Licence

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

en_CA

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14776/7271

OAI identifier oai:identifier

oai:uwindsor.scholaris.ca:20.500.14776/7271