Fix overflowing lines.

[saga.git] / dyn.tex

diff --git a/dyn.tex b/dyn.tex
index f22d5d08d5ab48f28a4c8743789f914110f5868b..c0d97e6bc2f1e7e907dff4f371802eb840e61cfc 100644 (file)
--- a/dyn.tex
+++ b/dyn.tex
@@ -225,7 +225,7 @@ $AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two sequences $AuC$ and $vBv$.
 If there was only a~single occurrence of~$v$, then $v$~was a~leaf and thus the sequence
 transforms from $AuvuC$ to $AuC$ and $v$~alone.
 
-\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes the sequence from $vAwBwCv$ to $wBwCvAw$.
+\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes its ET-sequence from $vAwBwCv$ to $wBwCvAw$.
 If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
 the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
 
@@ -461,7 +461,7 @@ to attach two lists of edges attached to vertices instead of one, or by using a~
 \::Insert $f$ to~$F_0,\ldots,F_{\ell(f)}$.
 \endalgo
 
-\algn{$\<Replace>(uv,i)$ -- Search for an~replacement edge for~$uv$ at level~$i$}
+\algn{$\<Replace>(uv,i)$ -- Search for replacement for edge~$uv$ at level~$i$}
 \algo
 \algin An~edge~$uv$ to replace and a~level~$i$ such that there is no replacement
 at levels greater than~$i$.
@@ -471,8 +471,9 @@ at levels greater than~$i$.
 \:Enumerate non-tree edges incident with vertices of~$T_1$ and stored in ${\cal E}_i$.
   For each edge~$xy$, $x\in T_1$, do:
 \::If $y\in T_2$, remove~$xy$ from~${\cal E}_i$ and return it to the caller.
-\::Otherwise increase $\ell(xy)$ by one. This includes deleting~$xy$ from~${\cal E}_i$
-  and inserting it to~${\cal E}_{i+1}$.
+\::Otherwise increase $\ell(xy)$ by one.
+  \hfil\break
+  This includes deleting~$xy$ from~${\cal E}_i$ and inserting it to~${\cal E}_{i+1}$.
 \:If $i>0$, call $\<Replace>(xy,i-1)$.
 \:Otherwise return \<null>.
 \algout The replacement edge.
@@ -497,7 +498,7 @@ ET-trees. Additionally, we call \<Replace> up to $L$ times. The initialization o
 \<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
 increases.
 
-To bring the complexity of \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
+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)$.
 This does not hurt the complexity of insertions and deletions, but allows for faster queries.
 \qed
@@ -613,7 +614,7 @@ updated in time $\O(\log^2 n)$ amortized per operation.
 The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
 reduction whose properties are summarized in the following theorem:
 
-\thmn{MSF dynamization, Henzinger et al.~\cite{henzinger:twoec}, Holm et al.~\cite{holm:polylog}}
+\thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
 Suppose that we have a~decremental MSF algorithm with the following properties:
 \numlist\ndotted
 \:For any $a$,~$b$, it can be initialized on a~graph with~$a$ vertices and~$b$ edges.
@@ -636,7 +637,7 @@ Delete of a~non-tree edge is performed on all $A_i$'s containing it and the repl
 sought among the replacement edges found in these structures. The unused replacement edges then have
 to be reinserted back to the structure.
 
-The original reduction of Henzinger et al.~handles these reinserts by a~mechanism of batch insertions
+The original reduction of Henzinger et al.~\cite{henzinger:twoec} handles these reinserts by a~mechanism of batch insertions
 supported by their decremental structure, which is not available in our case. Holm et al.~have
 replaced it by a~system of auxiliary edges inserted at various places in the structure.
 We refer to the article \cite{holm:polylog} for details.