X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=dyn.tex;h=f07103ac08cc19f4d596c73cca1c8d1aee0545b5;hb=3ce379fec86d6348c80aa1d8c77fb64a0dbada13;hp=41a5e2de52da9cd1962aeec65e7fcb5dad9267c9;hpb=6617b4a0f42121f0525d461aab9e940e3a3181e1;p=saga.git diff --git a/dyn.tex b/dyn.tex index 41a5e2d..f07103a 100644 --- a/dyn.tex +++ b/dyn.tex @@ -68,8 +68,8 @@ therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the followi Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$. -Correctness of the former case follows immediately from the Theorem on Minimality by order -(\ref{mstthm}), because any $F'$-light would be also $F$-light, which is impossible as $F$~was +Correctness of the former case follows immediately from the Minimality Theorem (\ref{mstthm}), +because any $F'$-light would be also $F$-light, which is impossible as $F$~was minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma (\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$ @@ -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$. @@ -410,7 +410,7 @@ anyway.) } 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 @@ -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{$\(uv,i)$ -- Search for an~replacement edge for~$uv$ at level~$i$} +\algn{$\(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 $\(xy,i-1)$. \:Otherwise return \. \algout The replacement edge. @@ -497,7 +498,7 @@ ET-trees. Additionally, we call \ up to $L$ times. The initialization o \ costs $\O(\log n)$ per call, the rest is paid for by the edge level increases. -To bring the complexity of \ from $\O(\log n)$ down to $\O(\log n/\log\log n)$, +To bring the complexity of the operation \ 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 @@ -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)$ @@ -555,7 +556,7 @@ edges for~$e$, the lightest one is at the maximum level. \proof Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle -rule (\ref{cyclerule}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$. +rule (Lemma \ref{redlemma}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$. In a~moment, we will show that the symmetric difference~$C$ of these two cycles is again a~cycle. This implies that if $f_1$ is heavier than~$f_2$, then $f_1$~is the heaviest edge on~$C$, so $\ell(f_1) \le \ell(f_2)$ by I3. Therefore the lightest of all replacement edges must have @@ -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. @@ -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 -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