diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 15 |
1 files changed, 7 insertions, 8 deletions
@@ -840,8 +840,8 @@ $W \subseteq V(T)$ is \definedterm{partition ready} if We will define the \definedterm{LCA partition with respect to $W$} for a partition ready subset $W$ of $T$'s vertices. The partition will assign each -vertex to a unique part, and each part will be rooted in an element of $W$ (in -particular, there will be as many parts as elements in $W$). +vertex of $T$ to a unique part, and each part will be rooted in an element of +$W$ (in particular, there will be as many parts as elements in $W$). Each part will be of one of three types: @@ -890,11 +890,10 @@ singletons constructed according to the following rules: }\label{partition-figure} \end{figure} -See Figure \ref{partition-figure} for an example of a partitioned tree. - 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 +$W$. See Figure \ref{partition-figure} for an example of a partitioned tree. +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 @@ -926,8 +925,8 @@ 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 \ref{partition-ready-last-step}, otherwise property \ref{both-subtrees-property} of partition readiness won't be satisfied. What we will show is that no other -new vertices need to be added. Take $v \in W''$ that had descendants in $W''$ in -both its subtrees, let $v_l$ and $v_r$ be its left and right child, +new vertices need to be added. Take $v \in W''$ that had descendants from $W''$ +in both its subtrees, let $v_l$ and $v_r$ be its left and right child, respectively. Without loss of generality, suppose $v_l$ was not an element of $W''$. The only reason we would need to add even more vertices after adding $v_l$ would be if $v_l$ had descendants in both its children's subtrees in @@ -1078,7 +1077,7 @@ components: \end{figure} $w$ is not a part of the subtree with hole, but we will need to consider it -during the following computation, so for ease of notation we will let $u_0 = +during the following computation, so for ease of notation we will define $u_0 := w$, extending the path of $u_i$'s. Figure \ref{subtree-with-hole-figure} depicts a subtree with hole labeled |