Off-Line Lowest Common Ancestor: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 31: Line 31:
|}
|}


== Time Complexity graph ==  
== Time Complexity Graph ==  


[[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Time.png|1000px]]
[[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Time.png|1000px]]


== Space Complexity graph ==  
== Space Complexity Graph ==  


[[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Space.png|1000px]]
[[File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Space.png|1000px]]


== Pareto Decades graph ==  
== Pareto Frontier Improvements Graph ==  


[[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 14:04, 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

Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Time.png

Space Complexity Graph

Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Space.png

Pareto Frontier Improvements Graph

Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Pareto Frontier.png