Finding Lowest Common Ancestors in Parallel
- 1 August 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (8) , 764-769
- https://doi.org/10.1109/tc.1986.1676830
Abstract
Two parallel algorithms for finding the lowest common ancestors of a set of vertex pairs Q (the query set) in a directed tree are presented. With all the overheads taken into account, these algorithms take O((n + QI) P log2 n) and O(n2/p + log2n) time, respectively, with p(> 0) processors (n is the size of the tree). These results are better than the best known result in that the first achieves the O(log2 n) time bound with only n + |Q| processors while the second reduces the number of processors used by a factor of log2 n which is optimal for large query sets when 0 < p ≤ n2/log2 n. The computer model we use here is the PRAM which is an SIMD model allowing read but not write conflicts. Our results also imply the following improvements: the processor bound for finding a set of fundamental cycles in an undirected graph is improved by a factor of log2 n and the result is optimal for dense graphs; the implementations of some other sequential and parallel algorithms are also simplified.Keywords
This publication has 9 references indexed in Scilit:
- Efficient Parallel Algorithms for a Class of Graph Theoretic ProblemsSIAM Journal on Computing, 1984
- Parallel Algorithms in Graph Theory: Planarity TestingSIAM Journal on Computing, 1982
- Routing, merging and sorting on parallel models of computationPublished by Association for Computing Machinery (ACM) ,1982
- Fast, Efficient Parallel Algorithms for Some Graph ProblemsSIAM Journal on Computing, 1981
- A linear time algorithm for the lowest common ancestors problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- An Efficient Method for Storing Ancestor Information in TreesSIAM Journal on Computing, 1979
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- On Finding Lowest Common Ancestors in TreesSIAM Journal on Computing, 1976
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence EquationsIEEE Transactions on Computers, 1973