From e370c3cd380880bb53a7cac4b4e1a185c39892d1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 3 May 2008 19:49:25 +0200 Subject: [PATCH] Corrections: The rest of Chapter 5. --- dyn.tex | 74 +++++++++++++++++++++++++++++---------------------------- 1 file changed, 38 insertions(+), 36 deletions(-) diff --git a/dyn.tex b/dyn.tex index 9f4cc7a..08f0904 100644 --- a/dyn.tex +++ b/dyn.tex @@ -414,7 +414,7 @@ anyway.) } At the beginning, the graph contains no edges, so both invariants are trivially -satisfied. Newly inserted edges can enter level~0, which cannot break I1 nor~I2. +satisfied. Newly inserted edges 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 @@ -422,14 +422,14 @@ smaller one. We will try to find the replacement edge of the highest possible 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. +at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can move all level~$\ell$ +edges of~$T_1$ to level~$\ell+1$ without violating either invariant. 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 +will be the grist for the mill of our amortization argument: We can charge most of the work on 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 @@ -437,8 +437,8 @@ lower level and so on. If there is no replacement edge at level~0, the tree~$T$ remains disconnected. \impl -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. +For each level~$\ell$, we will use a~separate ET-tree ${\cal E}_\ell$ with~$a$ set to~2, +which will represent the forest~$F_\ell$ 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. @@ -483,7 +483,7 @@ at levels greater than~$i$. \algout The replacement edge. \endalgo -\>As promised, time complexity will be analysed by amortization on the levels. +\>As foretold, 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 per @@ -522,7 +522,7 @@ to fit our needs, so we omit the details. \section{Dynamic spanning forests}\id{dynmstsect}% -Let us turn our attention back to the dynamic MSF now. +Let us turn our attention back to the dynamic MSF. 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 @@ -541,8 +541,8 @@ MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we ne the lightest possible choice. We will therefore use the weighted version of the ET-trees (Corollary \ref{wtet}) 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: +light edges tend to ``bubble up'' in the hierarchy of levels. This can be formalized +in form of the following invariant: {\narrower \def\iinv{{\bo I\the\itemcount~}} @@ -574,7 +574,7 @@ and the edge~$f_i$. Thus~$C$ must contain the paths $F[f_1^a,f_2^a]$ and $F[f_1^ 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 indeed observed: +We now have to make sure that the additional invariant is really observed: \lemma\id{ithree}% After every operation, the invariant I3 is satisfied. @@ -591,7 +591,7 @@ edge incident with some tree~$T_1$ at level $\ell=\ell(e)$. 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$, so the violation cannot occur. -Let us first show this for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself +Let us first show that for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself already are at the higher levels as they were moved there at the very beginning of the search for the replacement edge. The other tree edges incident with~$T_1$ would have lower levels, which is impossible since the invariant would be already violated. @@ -637,7 +637,7 @@ edge is contained in exactly one~$A_i$, tree edges can belong to multiple struct When an~edge is inserted, we union it with some of the $A_i$'s, build a~new decremental structure and amortize the cost of the build over the insertions. Deletes of non-tree edges are trivial. -Delete of a~non-tree edge is performed on all $A_i$'s containing it and the replacement edge is +Delete of a~tree edge is performed on all $A_i$'s containing it and the replacement edge is sought among the replacement edges found in these structures. The unused replacement edges then have to be reinserted back to the structure. @@ -668,7 +668,7 @@ We could try increasing the level of the newly inserted edge, but we would quite likely hit I1 before we managed to skip the levels of all the heaviest edges on the particular cycles. -On the other hand, if we decided to drop I3, we would encounter different problems. The ET-trees can +On the other hand, if we decided to drop I3, we would encounter different obstacles. The ET-trees can bring the lightest non-tree incident with the current tree~$T_1$, but the lightest replacement edge 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. @@ -677,7 +677,7 @@ An~interesting special case in which insertions are possible is when all non-tre edges have the same weight. This leads to the following algorithm for dynamic MSF on~graphs with a~small set of allowed edge weights. It is based on an~idea similar to the $\O(k\log^3 n)$ algorithm of Henzinger and King \cite{henzinger:randdyn}, -but adapted to use the better results on dynamic connectivity we have at hand. +but have adapted it 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 @@ -686,21 +686,19 @@ 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 +weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm to maintain an~arbitrary spanning forest~$F_1$ of~$G_1$, which is obviously minimum. Then we add another instance~$\C_2$ to maintain a~spanning forest~$F_2$ of the graph $G_2\cup F_1$ such that all edges of~$F_1$ are forced to be in~$F_2$. Obviously, $F_2$~is the MSF of the whole graph~$G$ --- if any edge of~$F_1$ were not contained in~$\msf(G)$, -we could use the standard exchange argument to create an~even lighter spanning tree.\foot{This -is of course the Blue lemma in action, but we have to be careful as we did not have proven it -for graphs with multiple edges of the same weight.} +we could use the standard exchange argument to create an~even lighter spanning tree. When a~weight~2 edge is inserted to~$G$, we insert it to~$\C_2$ and it either enters~$F_2$ or becomes a~non-tree edge. Similarly, deletion of a~weight~2 edge is a~pure deletion in~$\C_2$, because such edges can be replaced only by other weight~2 edges. Insertion of edges of weight~1 needs more attention: We insert the edge to~$\C_1$. If~$F_1$ -stays unchanged, we are done. If the new edge enters~$F_1$, we use Sleator-Tarjan trees +stays unchanged, we are done. If the new edge enters~$F_1$, we use a~Sleator-Tarjan tree kept for~$F_2$ to check if the new edge covers some tree edge of weight~2. If this is not the case, we insert the new edge to~$\C_2$ and hence also to~$F_2$ and we are done. Otherwise we exchange one of the covered weight~2 edges~$f$ for~$e$ in~$\C_2$. We note @@ -745,7 +743,7 @@ which are either present in all $K$ trees or in none of them. We will show a~variant of their algorithm based on the MST verification procedure of Section~\ref{verifysect}. -In this section, we will require the edge weights to be real numbers (or integers), because +In this section, we will require the edge weights to be numeric, because comparisons are certainly not sufficient to determine the second best spanning tree. We will assume that our computation model is able to add, subtract and compare the edge weights in constant time. @@ -763,7 +761,7 @@ For each $i>1$ there exists $j