Lowest Common Ancestor with Linking: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Lowest Common Ancestor with Linking (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 queries are on-line. Interspersed with the queries are on-line commands $link(x, y)$ such that $y$, but not necessarily $x$, is a tree root. The effect of a command $link(x, y)$ is to combine the trees containing $...") |
No edit summary |
||
| 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 == | ||
Revision as of 13:02, 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 queries are on-line. Interspersed with the queries are on-line commands $link(x, y)$ such that $y$, but not necessarily $x$, is a tree root. The effect of a command $link(x, y)$ is to combine the trees containing $x$ and $y$ by making $x$ the parent of $y$.
Related Problems
Generalizations: Lowest Common Ancestor
Related: Off-Line Lowest Common Ancestor, Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, 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 |
|---|---|---|---|---|---|---|
| Aho, Hopcroft, and Ullman (Linking) | 1976 | $O((m+n)$*log(n)) | $O(n*log(n)$) | Exact | Deterministic | Time & Space |
| Sleator and Tarjan (Linking) | 1983 | $O(n+m*log(n)$) | $O(n)$ | Exact | Deterministic | Time & Space |