Date of Award
2010
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Applied sciences
Supervisor
Yung H. Tsin
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
A parallel algorithm for finding 3-edge-connected components of an undirected graph on a CRCW PRAM is presented. The time and work complexity of this algorithm is O(logn) and O((m+n)loglogn), respectively, where n is the number of vertices and m is the number of edges in the input graph. The algorithm is based on ear decomposition and reduction of 3-edge-connectivity to 1-vertex-connectivity. This is the first 3-edge-connected component algorithm of a parallel model.
Recommended Citation
Ru, Yuan, "Finding 3-edge-connected components in parallel" (2010). Electronic Theses and Dissertations. 7917.
https://scholar.uwindsor.ca/etd/7917