Finding Triconnected Components by Local Replacement
Donald S. Fussell, Vijaya Ramachandran, Ramakrishna Thurimella · SIAM Journal on Computing · 1993
A parallel algorithm for finding triconnected components on a CRCW PRAM is presented. The time complexity of the algorithm is $O(\log n)$, and the processor-time product is $O((m + n)\log \log n)$, where n is the number of vertices and m is the number of edges of the input graph. The algorithm, like other parallel algorithms for this problem, is based on open ear decomposition, but it uses a new technique, local replacement, to improve the complexity. Only the need to use the subroutines for connected components and integer sorting, for which no optimal parallel algorithm that runs in $O(\log n)$ time is known, prevents the algorithm from achieving optimality.