Lowest Common Ancestor

Description

Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?"

Related Problems

Subproblem: Off-Line Lowest Common Ancestor, Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestor with Linking, Lowest Common Ancestors with Linking and Cutting

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

Parameters

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
Schieber; Vishkin	1988	$O(n+m)$	$O(n)$	Exact	Deterministic	Time & Space
Berkman; Vishkin	1993	$O(n+m)$ ?	$O(n)$	Exact	Deterministic	Time
[[Bender; Colton (LCA <=> RMQ) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor)|Bender; Colton (LCA <=> RMQ)]]	2000	$O(n+m)$	$O(n)$	Exact	Deterministic	Time
Stephen Alstrup, Cyril Gavoille, Haim Kaplan & Theis Rauhe	2004	$O(n+m)$	$O(n)$	Exact	Deterministic	Time
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
Aho, Hopcroft, and Ullman (Static Trees)	1976	$O((m+n)$*log(log(n)))	$O(n*log(log(n)$))	Exact	Deterministic	Time & Space
Aho, Hopcroft, and Ullman (Linking)	1976	$O((m+n)$*log(n))	$O(n*log(n)$)	Exact	Deterministic	Time & Space
Modified van Leeuwen (Static Trees)	1976	$O(n+m*log(log(n)$))	$O(n)$	Exact	Deterministic	Space
Modified van Leeuwen (Linking Roots)	1976	$O(n+m*log(log(n)$))	$O(n)$	Exact	Deterministic	Space
Sleator and Tarjan (Linking)	1983	$O(n+m*log(n)$)	$O(n)$	Exact	Deterministic	Time & Space
Sleator and Tarjan (Linking and Cutting)	1983	$O(n+m*log(n)$)	$O(n)$	Exact	Deterministic	Time & Space
Harel, Tarjan (Static Trees)	1984	$O(n+m)$	$O(n)$	Exact	Deterministic	Time & Space
Harel, Tarjan (Linking Roots)	1984	$O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function	$O(n)$	Exact	Deterministic	Time & Space
Schieber; Vishkin (Parallel)	1988	$O(m+log(n)$)	$O(n)$ total (auxiliary?)	Exact	Parallel	Time & Space
Fischer, Heun	2006	$O(m+n)$	$O(n)$	Exact	Parallel	Time & Space
Kmett	2015	$O(m*log(h)$)		Exact	Parallel	Time

Time Complexity Graph

Space Complexity Graph

Space-Time Tradeoff Improvements