From 5a53fb27895eb079336a20d6e4b6068a2917b4e9 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Apr 2008 17:49:16 +0200 Subject: [PATCH] Bug fixes to fully dynamic algorithms. --- dyn.tex | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) diff --git a/dyn.tex b/dyn.tex index 33c4b44..3024256 100644 --- a/dyn.tex +++ b/dyn.tex @@ -503,14 +503,14 @@ This does not hurt the complexity of insertions and deletions, but allows for fa \qed \rem -An~$\Omega(\log n/\log\log n)$ lower bound for amortized complexity of the dynamic connectivity +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 indexing of arrays.) So far, it is not known how to extend this algorithm +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. %-------------------------------------------------------------------------------- @@ -595,18 +595,19 @@ as~candidates for the replacement edge, because the algorithm always picks the l 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 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. +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 -\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}} 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. +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 -- 2.39.5