X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=dyn.tex;h=f07103ac08cc19f4d596c73cca1c8d1aee0545b5;hb=2673d7b09e7049aa35f3f81b6e7b395c934bdfbd;hp=31beea1512fdc08871444b16d9fffda9cee3f2bf;hpb=a41bbc241e18a0dbf262ada06df9199aced0b682;p=saga.git diff --git a/dyn.tex b/dyn.tex index 31beea1..f07103a 100644 --- 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$. @@ -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)$ @@ -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