AbstractThis paper gives a CREW PRAM algorithm for the problem of finding lowest common ancestors in a forest under the insertion of leaves and roots and the deletion of leaves. For a forest with a maximum of n vertices, the algorithm takes O(m/p + r log p + min(m, r log n)) time and O(n) space using p processors to process a sequence of m operations that are presented over r rounds. Furthermore, lowest common ancestor queries can be done in worst case constant time using a single processor. For one processor, the algorithm matches the bounds achieved by the best sequential algorithm known.
Categories and Subject Descriptors: E.1 [Data Structures]
Additional Key Words and Phrases: data structures
Selected references
- Omer Berkman and Uzi Vishkin. Recursive *-tree parallel data-structure (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 196-202, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Harold N. Gabow, Jon Louis Bentley, and Robert E. Tarjan. Scaling and related techniques for geometry problems. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 135-143, Washington, D.C., 1984.
- John H. Reif. An optimal parallel algorithm for integer sorting. In 26th Annual Symposium on Foundations of Computer Science, pages 496-504, Portland, Oregon, 21-23 October 1985. IEEE.