diff options
Diffstat (limited to 'mgr.tex')
-rw-r--r-- | mgr.tex | 14 |
1 files changed, 14 insertions, 0 deletions
@@ -1059,6 +1059,20 @@ components: doesn't lie on the $w$ to $v$ path. \end{itemize} +\begin{figure} + \centering + \def\svgwidth{0.5\columnwidth} + \input{subtree-with-hole.pdf_tex} + \caption{ + The subtree of $v$ with hole $w$. All its nodes can be partitioned into + the path $u_1, \ldots, u_4 = v$ and the subtrees of $u_1', \ldots, + u_4'$. + }\label{subtree-with-hole-figure} +\end{figure} + +Figure \ref{subtree-with-hole-figure} depicts a subtree with hole labeled +according to this nomenclature. + With our bottom-up computation, we've already computed the new state in $w$. There have been no relabelings in the subtrees of the $u_i'$'s, so we can get their states from the precomputed run of $A$ on the original tree. Now consider |