Date of Award

2007

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Rights

info:eu-repo/semantics/openAccess

Abstract

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.

Download

Share

COinS