scientific article; zbMATH DE number 4064469

From MaRDI portal
Publication:3798229





[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.











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)