Off-Line Lowest Common Ancestor: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Off-Line Lowest Common Ancestor (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$?" 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, ...") |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 13: | Line 13: | ||
== Parameters == | == Parameters == | ||
$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 24: | 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] | ||
|- | |- | ||
| [[Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor)|Aho, Hopcroft, and Ullman (Offline)]] || 1976 || $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/800125.804056 Time] & [https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf Space] | | [[Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor)|Aho, Hopcroft, and Ullman (Offline)]] || 1976 || $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/800125.804056 Time] & [https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf Space] | ||
| Line 30: | Line 31: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Time.png|1000px]] | [[File:Lowest Common Ancestor - Off-Line 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$?" 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
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 |
| 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
