Larger cover letters.

[saga.git] / dyn.tex

diff --git a/dyn.tex b/dyn.tex
index 31beea1512fdc08871444b16d9fffda9cee3f2bf..f07103ac08cc19f4d596c73cca1c8d1aee0545b5 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.
 
 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$.
 
 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$.
 


@@ -410,7 +410,7 @@ anyway.)
 }
 
 At the beginning, the graph contains no edges, so both invariants are trivially
 }
 
 At the beginning, the graph contains no edges, so both invariants are trivially

-satistifed. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.
+satisfied. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.

 
 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
 
 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the


@@ -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
 
 \::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$.
 \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.
 \: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.
 \: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.
 
 \<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
 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


@@ -515,7 +516,7 @@ to fit our needs, so we omit the details.
 
 %--------------------------------------------------------------------------------
 
 
 %--------------------------------------------------------------------------------
 

-\section{Dynamic spanning forests}
+\section{Dynamic spanning forests}\id{dynmstsect}%

 
 Let us turn our attention back to the dynamic MSF now.
 Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
 
 Let us turn our attention back to the dynamic MSF now.
 Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$


@@ -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:
 
 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.
 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.
 
 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.
 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.


@@ -676,8 +677,9 @@ but adapted to use the better results on dynamic connectivity we have at hand.
 
 \paran{Dynamic MSF with limited edge weights}%
 Let us assume for a~while that our graph has edges of only two different weights (let us say
 
 \paran{Dynamic MSF with limited edge weights}%
 Let us assume for a~while that our graph has edges of only two different weights (let us say

-1~and~2). We will forget our rule that all edge weights are distinct for a~moment and we recall that
-the basic structural properties of the MST's from Section \ref{mstbasics} still hold.
+1~and~2). We will forget our rule that all edge weights are distinct for a~moment and we recall
+the observation in \ref{multiweight} that the basic structural properties of
+the MST's from Section \ref{mstbasics} still hold.

 
 We split the graph~$G$ to two subgraphs~$G_1$ and~$G_2$ according to the edge
 weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm maintaining
 
 We split the graph~$G$ to two subgraphs~$G_1$ and~$G_2$ according to the edge
 weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm maintaining