Fussell, Donald; Ramachandran, Vijaya; Thurimella, Ramakrishna Finding triconnected components by local replacement. (English) Zbl 0778.05052 SIAM J. Comput. 22, No. 3, 587-616 (1993). Authors’ abstract: 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)\) times is known, prevents the algorithm from achieving optimality. Reviewer: P.Reichensperger (Oberasbach) Cited in 7 Documents MSC: 05C40 Connectivity 68W15 Distributed algorithms 90B18 Communication networks in operations research Keywords:vertex connectivity; parallel algorithm; triconnected components; PRAM; time complexity; graph; local replacement PDFBibTeX XMLCite \textit{D. Fussell} et al., SIAM J. Comput. 22, No. 3, 587--616 (1993; Zbl 0778.05052) Full Text: DOI