X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=inline;f=dyn.tex;h=f07103ac08cc19f4d596c73cca1c8d1aee0545b5;hb=2673d7b09e7049aa35f3f81b6e7b395c934bdfbd;hp=943231884c60976d8e78f875dd1d575772dbc9e3;hpb=b0982e0ec16f870a1f37dbe01c8b9e7da19656f4;p=saga.git diff --git a/dyn.tex b/dyn.tex index 9432318..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$ @@ -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. %-------------------------------------------------------------------------------- @@ -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$. @@ -401,39 +401,43 @@ 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 } 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 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,39 @@ 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$} +\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$. \: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. -\::Otherwise increase $\ell(xy)$ by one. This includes deleting~$xy$ from~${\cal E}_i$ - and inserting it to~${\cal E}_{i+1}$. +\::If $y\in T_2$, remove~$xy$ from~${\cal E}_i$ and return it to the caller. +\::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. \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. @@ -488,19 +498,31 @@ 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 +\rem +An~$\Omega(\log n/\log\log n)$ lower bound for the amortized complexity of the dynamic connectivity +problem has been proven by Henzinger and Fredman \cite{henzinger:lowerbounds} in the cell +probe model with $\O(\log n)$-bit words. Thorup has answered by a~faster algorithm +\cite{thorup:nearopt} that achieves $\O(\log n\log^3\log n)$ time per update and +$\O(\log n/\log^{(3)} n)$ per query on a~RAM with $\O(\log n)$-bit words. (He claims +that the algorithm runs on a~Pointer Machine, but it uses arithmetic operations, +so it does not fit the definition of the PM we use. The algorithm only does not +need direct indexing of arrays.) So far, it is not known how to extend this algorithm +to fit our needs, so we omit the details. + %-------------------------------------------------------------------------------- -\section{Dynamic MSF} +\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)$ 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 -operation, or $\O(k\log^3 n)$ if only~$k$ different values of edge weights are allowed. They have solved +operation, or $\O(k\log^3 n)$ if only $k$ different values of edge weights are allowed. They have solved the decremental version of the problem first (which starts with a~given graph and only edge deletions are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version. We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed @@ -508,12 +530,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,73 +548,79 @@ 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$. +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 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. +After every operation, the invariant 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. - -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 -considered as a~replacement 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$. - -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 -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 -other edges of~$C$ that are incident with~$T_1$. - -The case of edges that do not touch~$T_1$ is easy to handle: Such edges do not exist. -If they did, at least two edges of~$C$ would have to be non-tree edges connecting~$T_1$ -with the other trees at level~$\ell$, so one of them that is lighter than~$e$ would be selected as the -replacement edge before~$e$ could be considered. +to check only the replaces, in particular the place when an~edge~$e$ gets its level increased. + +For the violation to happen for the first time, $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 take place when~$e$ is considered as a~replacement +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 +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. +Non-tree edges of~$C$ incident with~$T_1$ are lighter than~$e$, so they were already considered +as~candidates for the replacement edge, because the algorithm always picks the lightest +candidate first. Such edges therefore have been already moved a~level up. + +The case of edges of~$C$ that do not touch~$T_1$ is easy to handle: Such edges do not exist. +If they did, at least one more edge of~$C$ besides~$e$ would have to connect~$T_1$ with the other +trees of level~$\ell$. We already know that this could not be a~tree edge. If it were a~non-tree +edge, it could not have level greater than~$\ell$ by~I1 nor smaller than~$\ell$ by~I3. Therefore +it would be a~level~$\ell$ edge lighter than~$e$, and as such it would have been selected as the +replacement edge before $e$~was. \qed We can conclude: \thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}} -When we start with a~graph with $n$~vertices and~$m\ge n$ edges and we perform -$d$~edge deletions, the MSF can be maintained in time $\O((m+d)\cdot\log^2 n)$. +When we start with a~graph on $n$~vertices with~$m$ edges and we perform a~sequence of +edge deletions, the MSF can be initialized in time $\O((m+n)\cdot\log^2 n)$ and then +updated in time $\O(\log^2 n)$ amortized per operation. \paran{Fully dynamic MSF}% The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox -reduction whose properties are summarized by the following theorem: +reduction whose properties are summarized in the following theorem: -\thmn{MSF dynamization, Henzinger et al.~\cite{henzinger:twoec}, Holm et al.~\cite{holm:polylog}} -Suppose that we have a~decremental MSF algorithm that for any $a$,~$b$ can be initialized -on a~graph with~$a$ vertices and~$b$ edges and then it executes an~arbitrary sequence -of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function. -Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting +\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. +\:Then it executes an~arbitrary sequence of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function. +\endlist +\>Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting with no edges, that performs $m$~insertions and deletions in amortized time: $$ \O\left( \log^3 n + \sum_{i=1}^{\log m} \sum_{j=1}^i \; t(\min(n,2^j), 2^j) \right) \hbox{\quad per operation.} @@ -600,7 +628,7 @@ $$ \proofsketch The reduction is very technical, but its essence is the following: We maintain a~logarithmic number -of decremental structures $A_0,\ldots,A_{\log n}$ of exponentially increasing sizes. Every non-tree +of decremental structures $A_0,\ldots,A_{\lfloor\log n\rfloor}$ of exponentially increasing sizes. Every non-tree edge is contained in exactly one~$A_i$, tree edges can belong to multiple structures. When an~edge is inserted, we union it with some of the $A_i$'s, build a~new decremental structure @@ -609,20 +637,20 @@ 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 the 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. \qed \corn{Fully dynamic MSF} -There is a~fully dynamic MSF algorithm that works in amortized time $\O(\log^4 n)$ +There is a~fully dynamic MSF algorithm that works in time $\O(\log^4 n)$ amortized per operation for graphs on $n$~vertices. \proof Apply the reduction from the previous theorem to the decremental algorithm we have -developed. This results in an~algorithm of amortized complexity $\O(\log^4 m)$ where~$m$ -is the number of operations performed. This could be more than $\O(\log^4 n)$ if +developed. This results in an~algorithm of amortized complexity $\O(\log^4\max(m,n))$ where~$m$ +is the number of operations performed. This could exceed $\O(\log^4 n)$ if $m$~is very large, but we can rebuild the whole structure after $n^2$~operations, which brings $\log m$ down to $\O(\log n)$. The $\O(n^2\log^4 n)$ cost of the rebuild then incurs only $\O(\log^4 n)$ additional cost on each operation. @@ -630,33 +658,31 @@ rebuild then incurs only $\O(\log^4 n)$ additional cost on each operation. \rem The limitation of MSF structures based on the Holm's algorithm for connectivity -to edge deletions only seems to be unavoidable. The invariant I3 could be easily +to only edge deletions seems to be unavoidable. The invariant I3 could be easily broken for many cycles at once whenever a~very light non-tree edge is inserted. We could try increasing the level of the newly inserted edge, but we would quite -possibly hit I1 before we skipped the levels of all the heavies edges on the +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. -We have enough time to scan all non-tree edges incident to the current tree~$T_1$ ---- we can charge it on the level increases of its tree edges and if we use the -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 -lower levels, which are too large to scan and both I1 and I2 prevent us from -charging the time on increasing levels there. +On the other hand, if we decided to drop I3, we would encounter different problems. 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. An~interesting special case in which insertions are possible is when all non-tree edges have the same weight. This leads to the following algorithm for dynamic MSF -on~graphs with a~small set of allowed edge weights. +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. \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 drop 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 to maintain +weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm maintaining 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 @@ -687,7 +713,7 @@ a~replacement in~$\C_2$. This way, we can handle every insertion and deletion in time $\O(\log^2 n)$ amortized. This construction can be iterated in an~obvious way: if we have $k$~distinct edge weights, we build $k$~connectivity structures $\C_1,\ldots,\C_k$. The structure~$\C_i$ contains edges of -weight~$i$ and the MSF edges from~$\C_{i-1}$. Bounding the time complexity is then easy: +weight~$i$ together with the MSF edges from~$\C_{i-1}$. Bounding the time complexity is then easy: \thmn{MSF with limited edge weights} There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized @@ -697,7 +723,8 @@ per operation for graphs on $n$~vertices with only $k$~distinct edge weights all A~change in the graph~$G$ involving an~edge of weight~$w$ causes a~change in~$\C_w$, which can propagate to~$\C_{w+1}$ and so on, possibly up to~$\C_k$. In each~$\C_i$, we spend time $\O(\log^2 n)$ by updating the connectivity structure according to -Theorem \ref{dyncon}. +Theorem \ref{dyncon} and $\O(\log n)$ on operations with the Sleator-Tarjan trees +by Theorem \ref{sletar}. \qed