Lowest Common Ancestor: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE: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$?" == 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...") |
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 12: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$?"
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
Currently no algorithms in our database for the given problem.
Time Complexity graph
Space Complexity graph
Pareto Decades graph
