From bf6ba465dda1426184f98e260be0e87e2b3dced8 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Apr 2008 13:07:14 +0200 Subject: [PATCH] More corrections. --- PLAN | 1 + dyn.tex | 78 ++++++++++++++++++++++++++++++++------------------------- 2 files changed, 45 insertions(+), 34 deletions(-) diff --git a/PLAN b/PLAN index 9357147..04d7887 100644 --- a/PLAN +++ b/PLAN @@ -116,3 +116,4 @@ Varia: - cite GA booklet - minimize the use of Remarks, use \paran instead +- formatting of multi-line \algin, \algout diff --git a/dyn.tex b/dyn.tex index 9432318..5aaee2a 100644 --- a/dyn.tex +++ b/dyn.tex @@ -185,7 +185,7 @@ from the Link-Cut tree, knowing that there is no edge to replace it). The hard p is the search for replacement edges after an~edge belonging to the MSF is deleted. This very problem also has to be solved by algorithms for fully dynamic connectivity, -we will take a~look on them first. +we will take a~look at them first. %-------------------------------------------------------------------------------- @@ -401,10 +401,11 @@ We will maintain the following \em{invariants:} {\narrower \def\iinv{{\bo I\the\itemcount~}} \numlist\iinv -\:$F$~is the maximum spanning forest of~$G$ with respect to the levels. In other words, -if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$. -\:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices. -This implies that all~$F_i$ for $i>L$ are empty. +\:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words, +if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.) +\:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each. +(This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty +anyway.) \endlist } @@ -414,26 +415,29 @@ satistifed. 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 smaller one. We will try to find the replacement edge of the highest possible -level that connects them back. From I1, we know that such an~edge cannot belong to -level greater than~$\ell$, so we start looking for it at level~$\ell$. According +level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to +a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can increase the levels of all edges of~$T_1$ without violating either invariant. -We now start enumerating the non-tree edges incident with~$T_1$. For each such edge, -we test whether its other endpoint lies in~$T_2$. If it does, we have found the replacement -edge and we insert it to~$F_\ell$. Otherwise we move the edge one level up. (This will -be the gist of our amortization argument: We can charge most of the work on level +We now start enumerating the non-tree edges incident with~$T_1$. Each such edge +is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge +whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement +edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This +will be the grist for the mill of our amortization argument: We can charge most of the work at level increases and we know that the level of each edge can reach at most~$L$.) If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next -lower level and so on. If there is no replacement edge on level~0, the tree~$T$ +lower level and so on. If there is no replacement edge at level~0, the tree~$T$ remains disconnected. \impl -We will use a~single ET-tree with~$a$ set to~2 for each level. For the $i$-th level, the ET-tree -${\cal E}_i$ will represent the forest~$F_i$ and the non-tree edges of -level~$i$ will be attached to its vertices. +For each level, we will use a~separate ET-tree ${\cal E}_\ell$ with~$a$ set to~2, +which will represent the forest~$F_i$ and the non-tree edges at that particular level. +Besides operations on the non-tree edges, we also need to find the tree edges of level~$\ell$ +when we want to bring them one level up. This can be accomplished either by modifying the ET-trees +to attach two lists of edges attached to vertices instead of one, or by using a~second ET-tree. \algn{Insertion of an~edge} \algo @@ -452,33 +456,38 @@ level~$i$ will be attached to its vertices. \:If $uv$ is a~non-tree edge: \::Remove $uv$ from the lists of non-tree edges at both $u$ and~$v$ in~${\cal E}_{\ell}$. \:Otherwise: -\::Remove $uv$ from~$F_\ell$. -\::Call $\(uv,\ell)$. +\::Remove $uv$ from~$F_\ell$ and hence also from $F_0,\ldots,F_{\ell-1}$. +\::Call $\(uv,\ell)$ to get the replacement edge~$f$. +\::Insert $f$ to~$F_0,\ldots,F_{\ell(f)}$. \endalgo \algn{$\(uv,i)$ -- Search for an~replacement edge for~$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$. \:Let $T_1$ and~$T_2$ be the trees in~$F_i$ containing $u$ and~$v$ respectively. \:If $n(T_1) > n(T_2)$, swap $T_1$ with~$T_2$. -\:Move all level~$i$ edges in~$T_1$ to level~$i+1$ and insert them to~${\cal E}_{i+1}$. +\:Find all level~$i$ edges in~$T_1$ using ${\cal E}_i$ and move them to level~$i+1$. \: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$, add the edge $xy$ to~$F_i$ and return. +\::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}$. \:If $i>0$, call $\(xy,i-1)$. +\:Otherwise return \. +\algout The replacement edge. \endalgo -\>Analysis of the time complexity is straightforward: +\>As promised, time complexity will be analysed by amortization on the levels. \thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}% -Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized for both +Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized per \ and \ and in time $\O(\log n/\log\log n)$ per \ in the worst case. \proof The direct cost of an~\ is $\O(\log n)$ for the operations on the ET-trees -(by Theorem \ref{etthm}). We will have it pre-pay all level increases of the new +(by Theorem \ref{etthm}). We will also have the insertion pre-pay all level increases of the new edge. Since the levels never decrease, each edge can be brought a~level up at most $L=\lfloor\log n\rfloor$ times. Every increase costs $\O(\log n)$ on the ET-tree operations, so we pay $\O(\log^2 n)$ for all of them. @@ -497,6 +506,7 @@ This does not hurt the complexity of insertions and deletions, but allows for fa \section{Dynamic MSF} +Let us turn our attention back to the dynamic MSF now. Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$ algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn} have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per @@ -508,12 +518,12 @@ the same path. They have modified their dynamic connectivity algorithm to solve in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation. \paran{Decremental MSF}% -Turning the algorithm from the previous section to decremental MSF requires only two +Turning the algorithm from the previous section to the decremental MSF requires only two changes: First, we have to start with the forest~$F$ equal to the MSF of the initial graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick the lightest possible choice. We will therefore use the weighted version of the ET-trees (Corollary \ref{wtet}) -and try the lightest non-tree edge incident with the examined tree first. We must ensure +and scan the lightest non-tree edge incident with the examined tree first. We must ensure that the lower levels cannot contain a~lighter replacement edge, but fortunately the light edges tend to ``bubble up'' in the hierarchy of levels. This can be formalized as the following invariant: @@ -526,38 +536,38 @@ the following invariant: \endlist } -\>This easily implies that we select the right replacement edge: +\>This immediately implies that we always select the right replacement edge: \lemma\id{msfrepl}% Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement -edges for~$e$, the lightest one is on the maximum level. +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$. 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 by I3 $f_1$~is the heaviest edge on~$C$, so -$\ell(f_1) \le \ell(f_2)$. Therefore the lightest of all replacement edges must have +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 the maximum level. Why is~$C$ a~cycle: Let $F^a$ and~$F^b$ be the trees of~$F-e$ in which the endpoints of~$e$ lie, and for -every edge~$g$ between $F^a$ and~$F^b$ let $g^a$ and~$g^b$ be its respective endpoints. +every edge~$g$ going between $F^a$ and~$F^b$ let $g^a$ and~$g^b$ be its respective endpoints. We know that $C_i$ consists of the path $F[f_i^a,e^a]$, the edge~$e$, the path $F[e^b,f_i^b]$, and the edge~$f_i$. Thus~$C$ must contain the paths $F[f_1^a,f_2^a]$ and $F[f_1^b,f_2^b]$ and the edges $f_1$ and~$f_2$, which together form a~simple cycle. \qed -We now have to make sure that the additional invariant is observed: +We now have to make sure that the additional invariant is indeed observed: \lemma\id{ithree}% After every operation, I3 is satisfied. \proof -When the structure is freshly initialized, I3 is obviously satisfied, because all edges +When the structure is freshly initialized, I3 is obviously satisfied, as all edges are at level~0. Sole deletions of edges (both tree and non-tree) cannot violate I3, so we need to check only the replaces, in particular when an~edge~$e$ either gets its level increased -or becomes a~tree edge. +or it becomes a~tree edge. For the violation to happen, $e$~must be the heaviest on some cycle~$C$, so by the Cycle rule, $e$~must be non-tree. The increase of $\ell(e)$ must therefore happen when~$e$ is @@ -566,7 +576,7 @@ We will pause the computation just before this increase and we will prove that all other edges of~$C$ already are at levels greater than~$\ell$. Let us first show that for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself -already are on the higher levels as they were moved there at the very beginning of the +already are at the higher levels as they were moved there at the very beginning of the search for the replacement edge. As the algorithm always tries the lightest candidate for the replacement edge first, all non-tree edges incident with~$T_1$ which are lighter than~$e$ were already considered and thus also moved one level up. This includes all @@ -642,7 +652,7 @@ We have enough time to scan all non-tree edges incident to the current tree~$T_1 degree reduction from Lemma \ref{degred}, there are at most two non-tree edges per vertex. (The reduction can be used dynamically as it always translates a~single change of the original graph to $\O(1)$ changes of the reduced graph.) The lightest -replacement edge however could also be located in the super-trees of~$T_1$ on the +replacement edge however could also be located in the super-trees of~$T_1$ at the lower levels, which are too large to scan and both I1 and I2 prevent us from charging the time on increasing levels there. -- 2.39.5