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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

This paper presents near-optimal deterministic parallel and distributedalgorithms for computing $(1+\varepsilon)$-approximate single-source shortestpaths in any undirected weighted graph.  On a high level, we deterministically reduce this and other shortest-pathproblems to $\tilde{O}(1)$ Minor-Aggregations. A Minor-Aggregation computes anaggregate (e.g., max or sum) of node-values for every connected component ofsome subgraph.  Our reduction immediately implies:  Optimal deterministic parallel (PRAM) algorithms with $\tilde{O}(1)$ depthand near-linear work.  Universally-optimal deterministic distributed (CONGEST) algorithms, wheneverdeterministic Minor-Aggregate algorithms exist. For example, an optimal$\tilde{O}(HopDiameter(G))$-round deterministic CONGEST algorithm forexcluded-minor networks.  Several novel tools developed for the above results are interesting in theirown right:  A local iterative approach for reducing shortest path computations "up todistance $D$" to computing low-diameter decompositions "up to distance$\frac{D}{2}$". Compared to the recursive vertex-reduction approach of [Li20],our approach is simpler, suitable for distributed algorithms, and eliminatesmany derandomization barriers.  A simple graph-based $\tilde{O}(1)$-competitive $\ell_1$-oblivious routingbased on low-diameter decompositions that can be evaluated in near-linear work.The previous such routing [ZGY+20] was $n^{o(1)}$-competitive and required$n^{o(1)}$ more work.  A deterministic algorithm to round any fractional single-source transshipmentflow into an integral tree solution.  The first distributed algorithms for computing Eulerian orientations.

Undirected $(1+\varepsilon)$-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms