×

zbMATH — the first resource for mathematics

On finding lowest common ancestors: Simplification and parallelization. (English) Zbl 0669.68049
Let T(V,E) be a rooted tree. The following problem arises: answer LCA queries of the form “Which vertex is the Lowest Common Ancestor (LCA) of x and y?” for any pair of vertices x,y in T. A simple, easily parallelizable, linear space and time algorithm that enables us answer each query in O(1) time is presented.
Reviewer: M.Kratko

MSC:
68R10 Graph theory (including graph drawing) in computer science
68W99 Algorithms in computer science
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI