Lowest Common Ancestor (Lowest Common Ancestor)
Revision as of 10:22, 15 February 2023 by Admin (talk | contribs) (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...")
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
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity graph
Error creating thumbnail: Unable to save thumbnail to destination
Pareto Decades graph
Error creating thumbnail: Unable to save thumbnail to destination