a new graphy triconnectivity algorithm and its parallelization
We present a new algorithm for finding the tri-connected components of an undirected graph. The algorithm is based on ear decomposition and has linear sequential running time. It also has a parallel implementation on a CRCW PRAM with O (log 2 n ) parallel time using a linear number of processors, where n is the number of vertices in the graph. This is the first efficient parallel algorithm for graph tri-connectivity.
graph algorithm parallel component decomposition timing implementation processor efficiency parallel algorithm connection