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

The All-Pairs Shortest Paths (APSP) problem is one of the fundamentalproblems in theoretical computer science. It asks to compute the distancematrix of a given $n$-vertex graph. We revisit the classical problem ofmaintaining the distance matrix under a \emph{fully-dynamic} setting undergoingvertex insertions and deletions with a fast \emph{worst-case} running time andefficient space usage.  Although amortized algorithm with $\tilde O(n ^ 2)$ update-time has beenknown for nearly two decades [Demetrescu and Italiano, STOC 2003], the currentbest algorithm for worst-case running time with efficient space usage runs isdue to [Gutenberg and Wulff-Nilsen, SODA 2020], which improves the space usageof the previous algorithm due to [Abraham, Chechik, and Krinninger, SODA 2017]to $\tilde O(n ^ 2)$ but fails to improve their running time of $\tilde O(n ^{2 + 2 / 3})$. It has been conjectured that no algorithm in $O(n ^ {2.5 -\epsilon})$ worst-case update time exists. For graphs without negative cycles,we meet this conjectured lower bound by introducing a Monte Carlo algorithmrunning in randomized $\tilde O(n ^ {2.5})$ time while keeping the $\tilde O(n^ 2)$ space bound from the previous algorithm. Our improvement is made possibleusing a novel multi-layer approach that exploits the gaps between hops (numberof vertices traversed) of paths.

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time