×

Fast parallel algorithms for a class of tree problems. (Chinese. English summary) Zbl 0751.68025

Summary: This paper presents some fast parallel algorithms for a class of tree problems. These problems include finding the path and the path length between two vertices in a tree, computing the depth of all vertices in a tree and etc. Based on these fundamental algorithms, this paper describes parallel algorithms for problems of finding the least common ancestor of two vertices in a tree, for edge updating dynamic minimum spanning tree problems and tree isomorphism problems. The model for parallel computation is a single-instruction stream multiple-data stream shared memory computer, allowing concurrent read but only exclusive write, which is known as CREW PRAM. All these algorithms run in \(O(\log n)\) time using \(O(n)\) processors, where \(n\) is the number of vertices in the tree. So according to the definition of Cook, we show these problems lie in the class NC.

MSC:

68W15 Distributed algorithms
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite