Lowest Common Ancestor: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 13: | Line 13: | ||
== Parameters == | == Parameters == | ||
n: number of vertices | $n$: number of vertices | ||
m: number of total number of operations (queries, links, and cuts) | $m$: number of total number of operations (queries, links, and cuts) | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 25: | Line 25: | ||
|- | |- | ||
| [[Tarjan's off-line lowest common ancestors algorithm (Off-Line Lowest Common Ancestor Lowest Common Ancestor)|Tarjan's off-line lowest common ancestors algorithm]] || 1984 || $O(n+m)$ || $O(n)$ || Exact || Deterministic || [https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174 Time | | [[Tarjan's off-line lowest common ancestors algorithm (Off-Line Lowest Common Ancestor Lowest Common Ancestor)|Tarjan's off-line lowest common ancestors algorithm]] || 1984 || $O(n+m)$ || $O(n)$ || Exact || Deterministic || [https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174 Time & Space] | ||
|- | |- | ||
| [[Schieber; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor)|Schieber; Vishkin]] || 1988 || $O(n+m)$ || $O(n)$ || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat Time | | [[Schieber; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor)|Schieber; Vishkin]] || 1988 || $O(n+m)$ || $O(n)$ || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat Time & Space] | ||
|- | |- | ||
| [[Berkman; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor)|Berkman; Vishkin]] || 1993 || $O(n+m)$ ? || $O(n)$ || Exact || Deterministic || [https://apps.dtic.mil/dtic/tr/fulltext/u2/a227803.pdf Time] | | [[Berkman; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor)|Berkman; Vishkin]] || 1993 || $O(n+m)$ ? || $O(n)$ || Exact || Deterministic || [https://apps.dtic.mil/dtic/tr/fulltext/u2/a227803.pdf Time] | ||
| Line 64: | Line 64: | ||
[[File:Lowest Common Ancestor - Time.png|1000px]] | [[File:Lowest Common Ancestor - Time.png|1000px]] | ||
Latest revision as of 09:08, 28 April 2023
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
