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 revisit the classic problem of dynamically maintaining shortest pathsbetween all pairs of nodes of a directed weighted graph. The allowed updatesare insertions and deletions of nodes and their incident edges. We giveworst-case guarantees on the time needed to process a single update (incontrast to related results, the update time is not amortized over a sequenceof updates).  Our main result is a simple randomized algorithm that for any parameter $c>1$has a worst-case update time of $O(cn^{2+2/3} \log^{4/3}{n})$ and answersdistance queries correctly with probability $1-1/n^c$, against an adaptiveonline adversary if the graph contains no negative cycle. The bestdeterministic algorithm is by Thorup [STOC 2005] with a worst-case update timeof $\tilde O(n^{2+3/4})$ and assumes non-negative weights. This is the firstimprovement for this problem for more than a decade. Conceptually, ouralgorithm shows that randomization along with a more direct approach canprovide better bounds.

Fully dynamic all-pairs shortest paths with worst-case update-time revisited