Off-Line Lowest Common Ancestor: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 39: | Line 39: | ||
[[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Space.png|1000px]] | [[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Space.png|1000px]] | ||
== | == Space-Time Tradeoff Improvements == | ||
[[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Pareto Frontier.png|1000px]] | [[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Pareto Frontier.png|1000px]] | ||
Revision as of 15:37, 15 February 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
Space Complexity Graph
Space-Time Tradeoff Improvements
