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

This paper presents parallel and distributed algorithms for single-sourceshortest paths when edges can have negative weights (negative-weight SSSP). Weshow a framework that reduces negative-weight SSSP in either setting to$n^{o(1)}$ calls to any SSSP algorithm that works with a virtual source. Morespecifically, for a graph with $m$ edges, $n$ vertices, undirected hop-diameter$D$, and polynomially bounded integer edge weights, we show randomizedalgorithms for negative-weight SSSP with (i) $W_{SSSP}(m,n)n^{o(1)}$ work and$S_{SSSP}(m,n)n^{o(1)}$ span, given access to an SSSP algorithm with$W_{SSSP}(m,n)$ work and $S_{SSSP}(m,n)$ span in the parallel model, (ii)$T_{SSSP}(n,D)n^{o(1)}$, given access to an SSSP algorithm that takes$T_{SSSP}(n,D)$ rounds in $\mathsf{CONGEST}$. This work builds off the recentresult of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives anear-linear time algorithm for negative-weight SSSP in the sequential setting.  Using current state-of-the-art SSSP algorithms yields randomized algorithmsfor negative-weight SSSP with (i) $m^{1+o(1)}$ work and $n^{1/2+o(1)}$ span inthe parallel model, (ii) $(n^{2/5}D^{2/5} + \sqrt{n} + D)n^{o(1)}$ rounds in$\mathsf{CONGEST}$.  Our main technical contribution is an efficient reduction for computing alow-diameter decomposition (LDD) of directed graphs to computations of SSSPwith a virtual source. Efficiently computing an LDD has heretofore only beenknown for undirected graphs in both the parallel and distributed models. TheLDD is a crucial step of the algorithm in [Bernstein, Nanongkai, Wulff-Nilsen,FOCS'22], and we think that its applications to other problems in parallel anddistributed models are far from being exhausted.

Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights