Off-Line Lowest Common Ancestor (Lowest Common Ancestor)
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.
Generalizations: Lowest Common Ancestor
$n$: number of vertices
$m$: number of total number of operations (queries, links, and cuts)
Table of Algorithms
|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|