English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

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$ areconstants. Note that there is a lower bound by Patrascu and Demaine (SIAM J.Comput. 2006) which shows that it takes $\Omega(\log n)$ time per operation tomaintain 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 thatdynamically maintains the $(1+\varepsilon)$-approximate weight of an MSFrequires super constant time per operation, if $W\geq (\log n)^{\omega_n(1)}$.  (2) Our randomized (Monte-Carlo style) algorithm works with high probabilityand 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 inthe graph throughout all the updates. It works even against an adaptiveadversary. 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 forany constant $\varepsilon,\alpha>0$ and $W=n^{\alpha}$, any (randomized) datastructure that dynamically maintains the weight of an MSF of a graph $G$ withedge weights in $[1,W]$ and $W = \Omega(\varepsilon m^*)$ within amultiplicative factor of $(1+\varepsilon)$ takes $\Omega(\log n)$ time peroperation.

Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest