Lowest Common Ancestor (Lowest Common Ancestor)

From Algorithm Wiki
Jump to navigation Jump to search

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

Error creating thumbnail: Unable to save thumbnail to destination