m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex27
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}