Clean up heavy vs. light vs. tree edges.

[saga.git] / adv.tex

diff --git a/adv.tex b/adv.tex
index 9c8177fd9c16f6a5a73bfee251214990294f245d..65d20294985e8ada129a24a8fc64ac00ddbd1e25 100644 (file)
--- a/adv.tex
+++ b/adv.tex
@@ -671,7 +671,7 @@ w(P_e[i])$.
 
 \alg $\<FindPeaks>(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 \<FindPeaks> procedure (Algorithm \ref{findheavy}) to find
+Then we run the \<FindPeaks> 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 \<FindPeaks>
-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}