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/

Zendy Plus

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

Zendy Tools

Zendy Open

We consider the problem of dynamically maintaining (approximate) all-pairseffective resistances in separable graphs, which are those that admit an$n^{c}$-separator theorem for some $c<1$. We give a fully dynamic algorithmthat maintains $(1+\varepsilon)$-approximations of the all-pairs effectiveresistances of an $n$-vertex graph $G$ undergoing edge insertions and deletionswith $\tilde{O}(\sqrt{n}/\varepsilon^2)$ worst-case update time and$\tilde{O}(\sqrt{n}/\varepsilon^2)$ worst-case query time, if $G$ is guaranteedto be $\sqrt{n}$-separable (i.e., it is taken from a class satisfying a$\sqrt{n}$-separator theorem) and its separator can be computed in$\tilde{O}(n)$ time. Our algorithm is built upon a dynamic algorithm formaintaining \emph{approximate Schur complement} that approximately preservespairwise effective resistances among a set of terminals for separable graphs,which might be of independent interest.  We complement our result by proving that for any two fixed vertices $s$ and$t$, no incremental or decremental algorithm can maintain the $s-t$ effectiveresistance for $\sqrt{n}$-separable graphs with worst-case update time$O(n^{1/2-\delta})$ and query time $O(n^{1-\delta})$ for any $\delta>0$, unlessthe Online Matrix Vector Multiplication (OMv) conjecture is false.  We further show that for \emph{general} graphs, no incremental or decrementalalgorithm can maintain the $s-t$ effective resistance problem with worst-caseupdate time $O(n^{1-\delta})$ and query-time $O(n^{2-\delta})$ for any $\delta>0$, unless the OMv conjecture is false.

Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs