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

Consider the following distance query for an $n$-node graph $G$ undergoingedge insertions and deletions: given two sets of nodes $I$ and $J$, return thedistances between every pair of nodes in $I\times J$. This query is rathergeneral and captures several versions of the dynamic shortest paths problem. Inthis paper, we develop an efficient $(1+\epsilon)$-approximation algorithm forthis query using fast matrix multiplication. Our algorithm leads to answers forsome open problems for Single-Source and All-Pairs Shortest Paths (SSSP andAPSP), as well as for Diameter, Radius, and Eccentricities. Below are somehighlights. Note that all our algorithms guarantee worst-case update time andare randomized (Monte Carlo), but do not need the oblivious adversaryassumption.  Subquadratic update time for SSSP, Diameter, Centralities, ect.: When we wantto maintain distances from a single node explicitly (without queries), afundamental question is to beat trivially calling Dijkstra's static algorithmafter each update, taking $\Theta(n^2)$ update time on dense graphs. It wasknown to be improbable for exact algorithms and for combinatorialany-approximation algorithms to polynomially beat the $\Omega(n^2)$ bound(under some conjectures) [Roditty, Zwick, ESA'04; Abboud, V. Williams,FOCS'14]. Our algorithm with $I=\{s\}$ and $J=V(G)$ implies a$(1+\epsilon)$-approximation algorithm for this, guaranteeing $\tildeO(n^{1.823}/\epsilon^2)$ worst-case update time for directed graphs withpositive real weights in $[1, W]$. With ideas from [Roditty, V. Williams,STOC'13], we also obtain the first subquadratic worst-case update time for$(5/3+\epsilon)$-approximating the eccentricities and$(1.5+\epsilon)$-approximating the diameter and radius for unweighted graphs(with small additive errors).  [...]

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time