From 880e8c60b2fb331131d34c4fa9a8873ef5b08205 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Apr 2008 14:12:38 +0200 Subject: [PATCH] Almost fixed the proof of I3. --- PLAN | 1 + dyn.tex | 31 +++++++++++++++++-------------- 2 files changed, 18 insertions(+), 14 deletions(-) diff --git a/PLAN b/PLAN index cc4fc6b..4b0f217 100644 --- a/PLAN +++ b/PLAN @@ -112,3 +112,4 @@ Varia: - cite GA booklet - minimize the use of Remarks, use \paran instead - formatting of multi-line \algin, \algout +- each chapter should make clear in which model we work diff --git a/dyn.tex b/dyn.tex index 4a8a1d8..33c4b44 100644 --- a/dyn.tex +++ b/dyn.tex @@ -521,7 +521,7 @@ 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 @@ -579,25 +579,28 @@ When the structure is freshly initialized, I3 is obviously satisfied, as all edg 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 the place when an~edge~$e$ gets its level increased. -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 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$. +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 that for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself +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. As the algorithm always picks the lightest candidate -for the replacement edge available, all non-tree edges incident with~$T_1$ that 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$. +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 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. +If they did, at least two edges of~$C$ would have to connect~$T_1$ with the other trees of level~$\ell$, +so one of them that is lighter than~$e$ would be selected as the replacement edge before~$e$ could be considered. \qed +\FIXME{The previous paragraph is incomplete, it does not take tree edges into account.} + We can conclude: \thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}} -- 2.39.2