论文标题
最小跨越森林的恒定时间动态重量近似
Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest
论文作者
论文摘要
我们提供了两种完全动态的算法，这些算法维持$（1+ \ varepsilon）$ - 最低跨度森林（MSF）的重量$ m $的近似$ n $ node Graph $ g $，EDG $ [1，w] $，对于任何$ \ varepsilon> 0 $ 0 $。 （1）我们的确定性算法take $ o（{w^2 \ log w}/{\ varepsilon^3}）$最差的更新时间，如果$ o（1）$是$ o（1）$，则如果$ w $和$ w $ \ varepsilon $都是常数。请注意，Patrascu和Demaine的下限（Siam J.Comput。2006）表明，每个操作都需要$ω（\ log n）$时间来维持即使在未加权的情况下也保持的MSF的确切权重，即$ W = 1 $。我们进一步表明，如果$ w \ geq（\ log n）^{ω_n（1）} $，MSF的$（1+ \ varepsilon）$的任何确定性数据结构都需要超级恒定的时间。 （2）我们的随机（蒙特 - 卡洛风格）算法具有很高的可能性，并且以最差的$ o（\ log w/\ w/\ varepsilon^{4}）$更新时间运行，如果$ w = o（{（m^*）所有更新。它甚至与自适应对手有关。这意味着每当$ w = \ min \ {o（（（m^*）^{1/6}/\ log^{2/3} n），2^{o（{\ log n}}} $和$ \ vareps的常数，我们通过表明，对于任何常数$ \ varepsilon，α> 0 $和$ w = n^α$，任何（随机的）数据结构，动态维持图形$ g $的重量，$ [1，w] $和$ w =ω n）每次操作$时间。
We give two fully dynamic algorithms that maintain a $(1+\varepsilon)$-approximation of the weight $M$ of a minimum spanning forest (MSF) of an $n$-node graph $G$ with edges weights in $[1,W]$, for any $\varepsilon>0$. (1) Our deterministic algorithm takes $O({W^2 \log W}/{\varepsilon^3})$ worst-case update time, which is $O(1)$ if both $W$ and $\varepsilon$ are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) which shows that it takes $Ω(\log n)$ time per operation to maintain the exact weight of an MSF that holds even in the unweighted case, i.e. for $W=1$. We further show that any deterministic data structure that dynamically maintains the $(1+\varepsilon)$-approximate weight of an MSF requires super constant time per operation, if $W\geq (\log n)^{ω_n(1)}$. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case $O(\log W/ \varepsilon^{4})$ update time if $W= O({(m^*)^{1/6}}/{\log^{2/3} n})$, where $m^*$ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. This implies a randomized algorithm with worst-case $o(\log n)$ update time, whenever $W=\min\{O((m^*)^{1/6}/\log^{2/3} n), 2^{o({\log n})}\}$ and $\varepsilon$ is constant. We complement this result by showing that for any constant $\varepsilon,α>0$ and $W=n^α$, any (randomized) data structure that dynamically maintains the weight of an MSF of a graph $G$ with edge weights in $[1,W]$ and $W = Ω(\varepsilon m^*)$ within a multiplicative factor of $(1+\varepsilon)$ takes $Ω(\log n)$ time per operation.
