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

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem inundirected edge-weighted graphs. Given an $n$-vertex graph $G$ withnon-negative edge lengths, that undergoes an online sequence of edge insertionsand deletions, the goal is to support approximate distance queries andshortest-path queries. We provide a deterministic algorithm for this problem,that, for a given precision parameter $\epsilon$, achieves approximation factor$(\log\log n)^{2^{O(1/\epsilon^3)}}$, and has amortized update time$O(n^{\epsilon}\log L)$ per operation, where $L$ is the ratio of longest toshortest edge length. Query time for distance-query is$O(2^{O(1/\epsilon)}\cdot \log n\cdot \log\log L)$, and query time forshortest-path query is $O(|E(P)|+2^{O(1/\epsilon)}\cdot \log n\cdot \log\logL)$, where $P$ is the path that the algorithm returns. To the best of ourknowledge, even allowing any $o(n)$-approximation factor, no adaptive-updatealgorithms with better than $\Theta(m)$ amortized update time and better than$\Theta(n)$ query time were known prior to this work. We also note that ourguarantees are stronger than the best current guarantees for APSP indecremental graphs in the adaptive-adversary setting.

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths