Lowest Common Ancestor with Static Trees (Lowest Common Ancestor)
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$?" In this version of the problem, the collection of trees is static but the queries are given on-line. That is, each query must be answered before the next one is known.
Related Problems
Generalizations: Lowest Common Ancestor
Related: Off-Line Lowest Common Ancestor, 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 |
|---|---|---|---|---|---|---|
| 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 (Static Trees) | 1976 | $O((m+n)$*log(log(n))) | $O(n*log(log(n)$)) | Exact | Deterministic | Time & Space |
| Modified van Leeuwen (Static Trees) | 1976 | $O(n+m*log(log(n)$)) | $O(n)$ | Exact | Deterministic | Space |
| Harel, Tarjan (Static Trees) | 1984 | $O(n+m)$ | $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
