diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 39 |
1 files changed, 37 insertions, 2 deletions
@@ -833,7 +833,7 @@ minimal partition ready set containing $W$. \subsection{Computing the LCA closure}\label{computing-closure} -\begin{lemma} +\begin{lemma}\label{lca-lemma} After linear preprocessing of a tree $T$, the LCA closure of a set of $m$ tree vertices $W \subseteq V(T)$ can be computed in time $O(m \log m)$, and the size of the closure is linear in the size of $W$. @@ -846,7 +846,7 @@ Now to compute the closure of $W$, we first sort the vertices in $W$ with respect to their in-order numbers, so we end up with a list $v_1, \ldots, v_m$ of vertices such that $\infixtable[v_1] < \ldots < \infixtable[v_m]$. -\begin{observation} +\begin{observation}\label{infix-observation} If $\infixtable[u] < \infixtable[v] < \infixtable[w]$, then $\mathlca(u, w)$ is equal to either $\mathlca(u, v)$ or $\mathlca(v, w)$. \end{observation} @@ -877,6 +877,41 @@ $U$ is of size $O(m)$ and can be computed in time $O(m)$ by issuing LCA queries to successive pairs of the sorted $W$. We claim that $W' := W \cup U$ is the LCA closure of $W$. +Let's define $u_i := LCA(v_i, v_{i+1})$. By Observation +\ref{lca-observation}, each $u_i$ falls between $v_i$ and $v_{i+1}$ in the infix +order, i.e. $W'$ sorted is the sequence $v_1, u_1, v_2, u_2, \ldots, u_{m - 1}, +v_m$ (note that in the way this sequence is written, some vertices might be +repeated, e.g. it might be the case that $LCA(v_2, v_3) = v_2$, in which case +$u_2$ will be equal to $v_2$). We claim that for every pair of vertices in $W'$, +their LCA is also in $W'$. We'll proceed by induction, and it will be easier if +we now rename the sorted $W'$ to $w_1 := v_1, w_2 := u_2, \ldots, w_{2m-2} := +u_{m-1}, w_{2m - 1} := v_m$. As quick recap, the following are properties of the +sequence of $w_i$'s: + +\begin{enumerate} + \item For $i < j$, $\infixtable[w_i] \leq \infixtable[w_j]$. + \item For odd $i$, $w_i$ comes from the original set $W$. + \item For even $i$, $w_i$ comes from the set of added vertices $U$. In + particular, $w_i$ is equal to $LCA(w_{i-1}, w_{i+1})$. +\end{enumerate} + +We prove that $W'$ is LCA closed by showing that for all pairs $w_i, w_j$, their +LCA belongs to $W'$, by induction on the difference between $i$ and $j$. + +The base case is to show that the LCA of $w_i$ and $w_{i+1}$ is in $W'$ for +every pair of successive vertices. Suppose $i$ is odd, then $w_{i+1}$ comes from +$U$ and was constructed as the LCA of $w_i$ and $w_{i+2}$. Then $w_{i+1}$ must +be on the path from $w_i$ to the root and is the LCA of the pair. Similarly for +when $i$ is even. + +Now assume that for all $w_i$, $w_j$, if $j - i < k$ then $LCA(w_i, w_j)$ is in +$W'$. We want to show the same is true when $j - i \leq k$. Take $w_i$ and $w_j$ +with $j - i = k$. Consider the triple $w_i$, $w_{i+1}$, $w_j$. By Observation +\ref{infix-observation}, $LCA(w_i, w_j)$ is equal to $LCA(w_i, w_{i+1})$ or +$LCA(w_{i+1}, w_j)$. By the induction assumption, we already know both of these +are in $W$, thus showing $W'$ is LCA closed and finishing the proof of Lemma +\ref{lca-lemma} + \section{Computing root states of parts} Let's now discuss how we will use LCA paritions to solve the relabel query |