




















We present a randomized algorithm for dynamic graph connectivity. With failure probability less than $1/n^c$ (for any constant $c$ we choose), our solution has worst case running time $O(\log^3 n)$ per edge insertion, $O(\log^4 n)$ per edge deletion, and $O(\log n/\log\log n)$ per query, where $n$ is the number of vertices. The previous best algorithm has worst case running time $O(\log^4 n)$ per edge insertion and $O(\log^5 n)$ per edge deletion. The improvement is made by reducing the randomness used in the previous result, so that we save a $\log n$ factor in update time. Specifically, \cite{kapron2013dynamic} uses $\log n$ copies of a data structure in order to boost a success probability from $1/2$ to $1-n^{-c}$. We show that, in fact though, because of the special structure of their algorithm, this boosting via repetition is unnecessary. Rather, we can still obtain the same correctness guarantee with high probability by arguing via a new invariant, without repetition.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。