From 178930710e13ff6db3bcf26cf57065070f8ae068 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 17 Mar 2008 14:40:12 +0100 Subject: [PATCH] Clean up heavy vs. light vs. tree edges. --- adv.tex | 6 +++--- mst.tex | 7 ++++--- 2 files changed, 7 insertions(+), 6 deletions(-) diff --git a/adv.tex b/adv.tex index 9c8177f..65d2029 100644 --- a/adv.tex +++ b/adv.tex @@ -671,7 +671,7 @@ w(P_e[i])$. \alg $\(u,p,T_p,P_p)$ --- process all queries in the subtree rooted at~$u$ entered from its parent via an~edge~$p$. -\id{findheavy} +\id{findpeaks} \algo \:Process all query paths whose bottom is~$u$ and record their peaks. @@ -766,7 +766,7 @@ of query paths in~$T$ (these are exactly the paths covered by the edges of $G\setminus T$). We use the reduction from Lemma \ref{verbranch} to get an~equivalent problem with a~full branching tree and a~set of parent-descendant paths. The reduction costs $\O(m+n)$ comparisons. -Then we run the \ procedure (Algorithm \ref{findheavy}) to find +Then we run the \ procedure (Algorithm \ref{findpeaks}) to find the tops of all query paths. According to Lemma \ref{vercompares}, this spends another $\O(m+n)$ comparisons. Since we (as always) assume that~$G$ is connected, $\O(m+n)=\O(m)$. \qed @@ -825,7 +825,7 @@ The reductions in Lemma \ref{verbranch} can be performed in time $\O(m)$. \para Having the reduced problem at hand, it remains to implement the procedure \ -of Algorithm \ref{findheavy} efficiently. We need a~compact representation of +of Algorithm \ref{findpeaks} efficiently. We need a~compact representation of the arrays $T_e$ and~$P_e$, which will allow to reduce the overhead of the algorithm to time linear will be linear in the number of comparisons performed. To achieve this goal, we will encode the arrays in RAM vectors (see Section \ref{bitsect} diff --git a/mst.tex b/mst.tex index 421fbc5..50e7bd2 100644 --- a/mst.tex +++ b/mst.tex @@ -75,12 +75,13 @@ Let~$T$ be a~spanning tree. Then: the edges of this path \df{edges covered by~$e$}. \:An edge~$e$ is called \df{light with respect to~$T$} (or just \df{$T$-light}) if it covers a heavier edge, i.e., if there is an edge $f\in T[e]$ such that $w(f) > w(e)$. -\:An edge~$e$ is called \df{$T$-heavy} if it is not $T$-light. +\:An edge~$e$ is called \df{$T$-heavy} if it covers a~lighter edge. \endlist \rem -Please note that the above properties also apply to tree edges -which by definition cover only themselves and therefore they are always heavy. +Edges of the tree~$T$ itself are neither heavy nor light. We will sometimes +use the name \df{non-heavy} for edges which are either light or contained +in the tree. \lemman{Light edges}\id{lightlemma}% Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$ -- 2.39.2