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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

With few exceptions (namely, algorithms for maximal matching, $2$-approximatevertex cover, and certain constant-stretch spanners), all known fully dynamicalgorithms in general graphs require (amortized) $\Omega(\log n)$ update/querytime. Showing for the first time that techniques from property testing can leadto constant-time fully dynamic graph algorithms we prove the following results:  (1) We give a fully dynamic (Las-Vegas style) algorithm with constantexpected amortized time per update that maintains a proper $(\Delta+1)$-vertexcoloring of a graph with maximum degree at most $\Delta$. This improves uponthe previous $O(\log \Delta)$-time algorithm by Bhattacharya et al. (SODA2018). We show that our result does not only have optimal running time, but isalso optimal in the sense that already deciding whether a $\Delta$-coloringexists in a dynamically changing graph with maximum degree at most $\Delta$takes $\Omega(\log n)$ time per operation.  (2) We give two fully dynamic algorithms that maintain a$(1+\varepsilon)$-approximation of the weight $M$ of the minimum spanningforest of a graph $G$ with edges weights in $[1,W]$. Our deterministicalgorithm takes $O({W^2 \log W}/{\varepsilon^3})$ worst-case time, which isconstant if both $W$ and $\varepsilon$ are constant. This is somewhatsurprising as a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006)shows that it takes $\Omega(\log n)$ time per operation to maintain the exactweight of the MSF that holds even for $W=1$. Our randomized (Monte-Carlo style)algorithm works with high probability and runs in worst-case$O(\frac{1}{\varepsilon^4}\log^2(\frac{1}{\varepsilon}))$ time if $W=O({(m^*)^{1/3}}/{\log^3 n})$, where $m^*$ is the minimum number of edges in thegraph throughout all the updates. It works even against an adaptive adversary.

Constant-Time Dynamic $(\Delta+1)$-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing