Fix overflowing lines.

[saga.git] / adv.tex

diff --git a/adv.tex b/adv.tex
index dc4e70fcbdadab8e14a3dd0bebe5d2105a69a144..d614c2583c2384137bbeb8634589e576442ff4ae 100644 (file)
--- a/adv.tex
+++ b/adv.tex
@@ -438,10 +438,10 @@ However the choice of the parameter~$t$ can seem mysterious, the following
 lemma makes the reason clear:
 
 \lemma\id{ijphase}%
-The $i$-th phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m)$.
+Each phase of the Iterated Jarn\'\i{}k's algorithm runs in time~$\O(m)$.
 
 \proof
-During the phase, the heap always contains at most~$t_i$ elements, so it takes
+During the $i$-th phase, the heap always contains at most~$t_i$ elements, so it takes
 time~$\O(\log t_i)=\O(m/n_i)$ to delete an~element from the heap. The trees~$R_i^j$
 are edge-disjoint, so there are at most~$n_i$ \<DeleteMin>'s over the course of the phase.
 Each edge is considered at most twice (once per its endpoint), so the number
@@ -667,7 +667,7 @@ As for every~$i$ the path $T[v,T_e[i+1]]$ is contained within $T[v,T_e[i]]$,
 the edges of~$P_e$ must have non-increasing weights, that is $w(P_e[i+1]) \le
 w(P_e[i])$.
 
-\alg $\<FindPeaks>(u,p,T_p,P_p)$ --- process all queries in the subtree rooted
+\alg $\<FindPeaks>(u,p,T_p,P_p)$ --- process all queries located in the subtree rooted
 at~$u$ entered from its parent via an~edge~$p$.
 \id{findpeaks}
 
@@ -1026,7 +1026,7 @@ determines whether~$T$ is minimum and finds all $T$-light edges in~$G$ in time $
 \proof
 Implement the Koml\'os's algorithm from Theorem \ref{verify} with the data
 structures developed in this section.
-According to Lemma \ref{verfh}, it runs in time $\sum_e \O(\log\vert T_e\vert + q_e)
+According to Lemma \ref{verfh}, the algorithm runs in time $\sum_e \O(\log\vert T_e\vert + q_e)
 = \O(\sum_e \log\vert T_e\vert) + \O(\sum_e q_e)$. The second sum is $\O(m)$
 as there are $\O(1)$ query paths per edge, the first sum is $\O(\#\hbox{comparisons})$,
 which is $\O(m)$ by Theorem \ref{verify}.