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 study computing {\em all-pairs shortest paths} (APSP) on distributednetworks (the CONGEST model). The goal is for every node in the (weighted)network to know the distance from every other node using communication. Theproblem admits $(1+o(1))$-approximation $\tilde O(n)$-time algorithms~\cite{LenzenP-podc15,Nanongkai-STOC14}, which are matched with $\tilde\Omega(n)$-time lowerbounds~\cite{Nanongkai-STOC14,LenzenP_stoc13,FrischknechtHW12}\footnote{$\tilde\Theta$, $\tilde O$ and $\tilde \Omega$ hide polylogarithmic factors. Note thatthe lower bounds also hold even in the unweighted case and in the weighted casewith polynomial approximation ratios.}. No $\omega(n)$ lower bound or $o(m)$upper bound were known for exact computation.  In this paper, we present an $\tilde O(n^{5/4})$-time randomized (Las Vegas)algorithm for exact weighted APSP; this provides the first improvement over thenaive $O(m)$-time algorithm when the network is not so sparse. Our result alsoholds for the case where edge weights are {\em asymmetric} (a.k.a. the directedcase where communication is bidirectional). Our techniques also yield an$\tilde O(n^{3/4}k^{1/2}+n)$-time algorithm for the {\em $k$-source shortestpaths} problem where we want every node to know distances from $k$ sources;this improves Elkin's recent bound~\cite{Elkin-STOC17} when $k=\tilde\omega(n^{1/4})$.

Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds