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 present a general toolbox, based on new vertex sparsifiers, for designingdata structures to maintain shortest paths in dynamic graphs.  In an $m$-edge graph undergoing edge insertions and deletions, our datastructures give the first algorithms for maintaining (a) $m^{o(1)}$-approximateall-pairs shortest paths (APSP) with \emph{worst-case} update time $m^{o(1)}$and query time $\tilde{O}(1)$, and (b) a tree $T$ that has diameter no largerthan a subpolynomial factor times the diameter of the underlying graph, whereeach update is handled in amortized subpolynomial time.  In graphs undergoing only edge deletions, we develop a simpler and moreefficient data structure to maintain a $(1+\epsilon)$-approximate single-sourceshortest paths (SSSP) tree $T$ in a graph undergoing edge deletions inamortized time $m^{o(1)}$ per update.  Our data structures are deterministic. The trees we can maintain are notsubgraphs of $G$, but embed with small edge congestion into $G$. This is instark contrast to previous approaches and is useful for algorithms thatinternally use trees to route flow.  To illustrate the power of our new toolbox, we show that our SSSP datastructure gives simple deterministic implementations of flow-routing MWUmethods in several contexts, where previously only randomized methods had beenknown.  To obtain our toolbox, we give the first algorithm that, given a graph $G$undergoing edge insertions and deletions and a dynamic terminal set $A$,maintains a vertex sparsifier $H$ that approximately preserves distancesbetween terminals in $A$, consists of at most $|A|m^{o(1)}$ vertices and edges,and can be updated in worst-case time $m^{o(1)}$.  Crucially, our vertex sparsifier construction allows us to maintain a lowedge-congestion embedding of $H$ into $G$, which is needed for ourapplications.

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications