Lowest Common Ancestor with Static Trees

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.

Parameters

$n$ : number of vertices
$m$ : number of total number of operations (queries, links, and cuts)

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 7 of 7 algorithms


Stephen Alstrup, Cyril Gavoille, Haim Kaplan & Theis Rauhe	2004	$O(n+m)$	$O(n)$
Bender; Colton [LCA <=> RMQ]	2000	$O(n+m)$	$O(n)$
Berkman; Vishkin	1993	$O(n+m)$	$O(n)$
Schieber; Vishkin	1988	$O(n+m)$	$O(n)$
Harel, Tarjan [Static Trees]	1984	O(n+m)	O(n)
Aho, Hopcroft, and Ullman [Static Trees]	1976	O((m+n)*log(log(n)))	O(n*log(log(n)))
Modified van Leeuwen [Static Trees]	1976	O(n+m*log(log(n)))	O(n)

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms