PLAN--

[saga.git] / dyn.tex

diff --git a/dyn.tex b/dyn.tex
index 08f0904168383c325ba7de729223c82612f7bb9e..95d9340cc4fd6ca82bd055fb9db5cdb9524cff6f 100644 (file)
--- a/dyn.tex
+++ b/dyn.tex
@@ -77,6 +77,7 @@ on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blu
 of~$F$ that contains both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls
 apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest in the cut~$\delta_G(T_1)$
 and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$.
+\looseness=1 %%HACK%%
 
 A~\<Delete> of an~edge that is not contained in~$F$ does not change~$F$. When we delete
 an~MSF edge, we have to reconnect~$F$ by choosing the lightest edge of the cut separating
@@ -254,6 +255,7 @@ initialization of the structure and with $b=2a$. We know from the standard theor
 (see for example \cite{clrs}) that the depth of a~tree with $n$~leaves is always $\O(\log_a n)$
 and that all basic operations including insertion, deletion, search, splitting and joining the trees
 run in time $\O(b\log_a n)$ in the worst case.
+\looseness=-1 %%HACK%%
 
 We will use the ET-trees to maintain a~spanning forest of the dynamic graph. The auxiliary data of
 each vertex will hold a~list of edges incident with the given vertex, that do not lie in the
@@ -374,10 +376,9 @@ We can therefore conclude:
 
 \corn{Weighted ET-trees}\id{wtet}%
 In weighted ET-trees, the operations \<InsertNontree> and \<DeleteNontree> have time
-complexity $\O(a\log_a n)$. All other operations take the same time as in Theorem
+complexity $\O(a\log_a n)$. All other operations take the same time as indicated by Theorem
 \ref{etthm}.
 
-
 %--------------------------------------------------------------------------------
 
 \section{Dynamic connectivity}
@@ -503,7 +504,7 @@ ET-trees. Additionally, we call \<Replace> up to $L$ times. The initialization o
 increases.
 
 To bring the complexity of the operation \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
-we apply the trick from Example \ref{accel} and store~$F_0$ in a~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
+we apply the trick from Example \ref{accel} and store~$F_0$ in an~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
 This does not hurt the complexity of insertions and deletions, but allows for faster queries.
 \qed
 
@@ -918,7 +919,7 @@ the edges $t_K,\ldots,t_{n-1}$ are present in all trees $T_2,\ldots,T_K$.
 The best exchanges in~$T_1$ involving $t_1,\ldots,t_{K-1}$ produce~$K-1$ spanning trees
 of increasing weights. Any exchange involving $t_K,\ldots,t_n$ produces a~tree
 which is heavier or equal than all those trees. (We are ascertained by the Monotone exchange lemma
-that the gain of such exchanges need not be reverted by any later exchanges.)
+that the gain of such exchanges need not be reverted later.)
 \qed
 
 \lemma\id{gainb}%