scientific article; zbMATH DE number 4064469
[For the entire collection see Zbl 0643.00025.] We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm which enables us to answer each query in O(1) time, as in \textit{D. Harel} and \textit{R. E. Tarjan} [SIAM J. Comput. 13, 338-355 (1984; Zbl 0535.68022)]. Our algorithm has the advantage of being simple and easily parallelizable. The resulting parallel preprocessing algorithm runs in logarithmic time using an optimal number of processors on an EREW PRAM. Each query is then answered in O(1) time using a single processor.
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- Data structures and algorithms for approximate string matching
- Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
- A fast cost-optimal parallel algorithm for the lowest common ancestor problem
- New algorithms for the LCA problem and the binary tree reconstruction problem
- Finding level-ancestors in trees
- Finding lowest common ancestors in arbitrarily directed trees
- Robust hierarchical feature selection driven by data and knowledge
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Fast smallest lowest common ancestor computation based on stable match
- Fast Algorithms for Finding Nearest Common Ancestors
- Simple parallel algorithms for dynamic range products
- Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
- Finding Lowest Common Ancestors in Parallel
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
- scientific article; zbMATH DE number 88972 (Why is no real title available?)
- scientific article; zbMATH DE number 753968 (Why is no real title available?)
- Parallel dynamic lowest common ancestors
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798229)