×

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
Full Text: DOI