Finding Lowest Common Ancestors in Parallel

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.