Off-Line Lowest Common Ancestor (Lowest Common Ancestor)

From Algorithm Wiki
Revision as of 09:08, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the collection of trees is static and the entire sequence of queries is specified in advance.

Related Problems

Generalizations: Lowest Common Ancestor

Related: Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestor with Linking, Lowest Common Ancestors with Linking and Cutting


$n$: number of vertices

$m$: number of total number of operations (queries, links, and cuts)

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Tarjan's off-line lowest common ancestors algorithm 1984 $O(n+m)$ $O(n)$ Exact Deterministic Time & Space
Aho, Hopcroft, and Ullman (Offline) 1976 $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function $O(n)$ Exact Deterministic Time & Space

Time Complexity Graph

Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Time.png