From 79e3a9b5190bac30770b5e27fe57e95ca6e85953 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 3 Dec 2021 18:22:28 +0100 Subject: Reword partition readiness --- mgr.tex | 29 +++++++++++++++-------------- 1 file changed, 15 insertions(+), 14 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 9328809..7bc1ef2 100644 --- a/mgr.tex +++ b/mgr.tex @@ -783,9 +783,9 @@ singletons constructed according to the following rules: were assigned to parts when its children were handled. \end{enumerate} -If $W$ is not parition ready, we will call the LCA partition with respect to $W$ -the partition with respect to the minimal partition ready set that contains $W$. -Skipping ahead, the LCA partition of the set of vertices relabeled in a +If $W$ is not parition ready, we will define the LCA partition with respect to +$W$ the partition with respect to the minimal partition ready set that contains +$W$. Skipping ahead, the LCA partition of the set of vertices relabeled in a relabeling question will be the partition we alluded to at the end of the previous section. We promised that this partition will have $O(m)$ parts, so we must show that for a set $W$, the minimal partition ready set containing it is @@ -809,9 +809,9 @@ Take a set of $m$ tree vertices $W$ and consider the following procedure: By defintition of LCA closure, $W''$ above is the smallest LCA closed set containing $W$ and the tree's root. Step \ref{partition-ready-last-step} adds at most $2|W''|$ new vertices, we will now prove that these are exactly the only -vertices still needed to be added to arrive at a partition ready set. That only -$O(m)$ vertices are added in step \ref{partition-ready-lca-step} will be proved in -the next section. +vertices still needed to be added to arrive at a partition ready set. For now +assume that only $O(m)$ vertices were added in step +\ref{partition-ready-lca-step}, this will be proved in the next section. It's easy to see that $W'''$ is still LCA closed. It is obvious that it is necessary to add at least all the vertices added in step @@ -825,11 +825,11 @@ $v_l$ would be if $v_l$ had descendants in both its children's subtrees in $W'''$. First let's show that it has descendants in $W''$ in at most one of its subtrees. Indeed, if it did have descendants from $W''$ in both its subtrees, $W''$ wouldn't have been LCA closed -- $v_l$ would have been the LCA of the -topmost members of $W''$ of its left and right subtrees. Note that newly added -elements of $W'''$ can appear only underneath vertices that were originally in -$W''$, so if $v_l$ didn't have an element of $W''$ in one of its subtrees, then -it also doesn't have elements of $W'''$ in that subtree. Thus $W'''$ is indeed -the minimal partition ready set containing $W$. +topmost members of $W''$ of its children's subtrees. Newly added elements of +$W'''$ can appear only underneath vertices that were originally in $W''$, so if +$v_l$ didn't have an element of $W''$ in one of its subtrees, then it also +doesn't have elements of $W'''$ in that subtree. Thus $W'''$ is indeed the +minimal partition ready set containing $W$. \subsection{Computing the LCA closure}\label{computing-closure} @@ -853,7 +853,7 @@ of vertices such that $\infixtable[v_1] < \ldots < \infixtable[v_m]$. This may be proved by a simple case analysis. -\begin{observation} +\begin{observation}\label{lca-observation} Consider two tree vertices, $u, w \in V(T)$ with $\infixtable[u] < \infixtable [w]$, and their least common ancestor $v$. Then $\infixtable[u] \leq \infixtable[v] \leq \infixtable[w]$. @@ -865,8 +865,9 @@ example, if $v = u$, we have that $\infixtable[u] = \infixtable[v] < and $w$ must be in its right subtree. Thus an infix walk over $T$ will first visit $u$, then $v$, and then $w$. -Now, once $W$ has been sorted by in-order numbers, we can complete our -computation in time $O(m)$. Consider the following set of vertices: +Now, once $W$ has been sorted by in-order numbers (which takes time $O(m \log +m)$ using a standard sorting algorithm), we can complete our computation in time +$O(m)$. Consider the following set of vertices: \begin{equation*} U := \{ v \;|\; v = LCA(v_i, v_{i+1}) \text{ for $1 \leq i \leq m - 1$} \} -- cgit v1.2.3