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 give new partially-dynamic algorithms for the all-pairs shortest pathsproblem in weighted directed graphs. Most importantly, we give a newdeterministic incremental algorithm for the problem that handles updates in$\widetilde{O}(mn^{4/3}\log{W}/\epsilon)$ total time (where the edge weightsare from $[1,W]$) and explicitly maintains a $(1+\epsilon)$-approximatedistance matrix. For a fixed $\epsilon>0$, this is the first deterministicpartially dynamic algorithm for all-pairs shortest paths in directed graphs,whose update time is $o(n^2)$ regardless of the number of edges. Furthermore,we also show how to improve the state-of-the-art partially dynamic randomizedalgorithms for all-pairs shortest paths [Baswana et al. STOC'02, BernsteinSTOC'13] from Monte Carlo randomized to Las Vegas randomized without increasingthe running time bounds (with respect to the $\widetilde{O}(\cdot)$ notation).  Our results are obtained by giving new algorithms for the problem ofdynamically maintaining hubs, that is a set of $\widetilde{O}(n/d)$ verticeswhich hit a shortest path between each pair of vertices, provided it hashop-length $\Omega(d)$. We give new subquadratic deterministic and Las Vegasalgorithms for maintenance of hubs under either edge insertions or deletions.

Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs