×

Finding triconnected components by local replacement. (English) Zbl 0778.05052

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.

MSC:

05C40 Connectivity
68W15 Distributed algorithms
90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI