Replace Schieber+Vishkin with Bender+Farah-Colton

1 files changed, 2 insertions, 25 deletions

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}