Improved distributed algorithms for exact shortest paths

DOI10.1145/3188745.3188948MaRDI QIDQ5230308zbMATH OpenOpenAlexWikidataFDO

Authors Mohsen Ghaffari, Jason Li

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.09121

zbMATH Keywords

distributed algorithmsshortest paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Analysis of algorithms (68W40)

Abstract: Computing shortest paths is one of the central problems in the theory of distributed computing. For the last few years, substantial progress has been made on the approximate single source shortest paths problem, culminating in an algorithm of Becker et al. [DISC'17] which deterministically computes $(1+o(1))$-approximate shortest paths in $ildeO(D+sqrtn)$ time, where $D$ is the hop-diameter of the graph. Up to logarithmic factors, this time complexity is optimal, matching the lower bound of Elkin [STOC'04]. The question of exact shortest paths however saw no algorithmic progress for decades, until the recent breakthrough of Elkin [STOC'17], which established a sublinear-time algorithm for exact single source shortest paths on undirected graphs. Shortly after, Huang et al. [FOCS'17] provided improved algorithms for exact all pairs shortest paths problem on directed graphs. In this paper, we present a new single-source shortest path algorithm with complexity $ildeO(n^{3/4}{D}^{1/4})$. For polylogarithmic $D$, this improves on Elkin's $ildeO(n^{5/6})$ bound and gets closer to the $ildeOmega(n^{1/2})$ lower bound of Elkin [STOC'04]. For larger values of $D$, we present an improved variant of our algorithm which achieves complexity $ildeOleft(n^{3/4+o(1)}+min{n}^{3/4}{D}^{1/6},n^{6/7}+Dight)$, and thus compares favorably with Elkin's bound of $ildeO(n^{5/6}+n^{2/3}{D}^{1/3}+D)$ in essentially the entire range of parameters. This algorithm provides also a qualitative improvement, because it works for the more challenging case of directed graphs (i.e., graphs where the two directions of an edge can have different weights), constituting the first sublinear-time algorithm for directed graphs. Our algorithm also extends to the case of exact $kappa$-source shortest paths...

Recommendations

• Faster distributed shortest path approximations via shortcuts
• An Improved Distribution Algorithm for Shortest Paths Problem
• Partially dynamic efficient algorithms for distributed shortest paths
• scientific article; zbMATH DE number 1512693
• scientific article; zbMATH DE number 749816
• Distributed algorithms for computing shortest pairs of disjoint paths
• Optimized versions of a distributed algorithm for solving path problems

Cited in

(22)

• Improvements for the thresh X2 shortest path algorithm
• Fast approximate shortest paths in the congested clique
• Single-source shortest paths in the CONGEST model with improved bounds
• The sparsest additive spanner via multiple weighted BFS trees
• A distributed algorithm for directed minimum-weight spanning tree
• Another adaptive distributed shortest path algorithm
• scientific article; zbMATH DE number 1512693 (Why is no real title available?)
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Faster distributed shortest path approximations via shortcuts
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Distributed approximation algorithms for weighted shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A novel pseudo‐polynomial approach for shortest path problems
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• Reachability and shortest paths in the broadcast CONGEST model
• Finding a small vertex cut on distributed networks
• Distributed planar reachability in nearly optimal time
• Distributed distance approximation
• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Distance computations in the hybrid network model via oracle simulations

This page was built for publication: Improved distributed algorithms for exact shortest paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230308)