From 28e9a9bfaa3ad8fb8f76b3feb2f571d388ad70fe Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Tue, 3 Aug 2021 18:13:53 +0200 Subject: Replace Schieber+Vishkin with Bender+Farah-Colton --- mgr.tex | 27 ++------------------------- 1 file changed, 2 insertions(+), 25 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 86217d9..aaeecd3 100644 --- a/mgr.tex +++ b/mgr.tex @@ -134,34 +134,11 @@ is the highest black node on the path between $x$ and $y$. We will build an index structure, constructible in linear time, that allows us to handle such queries in constant time. The structure is heavily inspired by -Schieber and Vishkin's structure for computing LCA queries. We will present our -version of the structue in full detail, using Schieber and Vishkin's notation -where possible. +Bender and Farach-Colton's presentation of an algorithm originally attributed to +Berkman and Vishkin for computing LCA queries. \subsection{High level overview} -The LCA algorithm given by Schieber and Vishkin bases on two observations, first -made by Harel and Tarjan: - -\begin{itemize} - \item LCA queries can be computed in constant time on \emph{simple paths}. - \item LCA queries can be computed in constant time on \emph{full binary trees}. -\end{itemize} - -We map vertices of our tree $T$ to vertices of a full binary tree $B$ of size -$O(n)$ that has two properties: - -\begin{enumerate} - \item The induced subgraph of all vertices mapped to the same node of $B$ is - a simple path in $T$. - \item If a vertex $v$ of $T$ is mapped to a vertex $b$ of $B$, all of its - descendants are mapped to descendants of $b$ (where $b$ is also a - descendant of itself). -\end{enumerate} - -From 2. we get that also all of $v$'s ancestors are mapped to $b$'s ancestors in -$B$, in particular they are all mapped into at most $\log(n)$ nodes of $B$. - \section{Generalizing words to trees} \chapter{Conclusions} -- cgit v1.2.3