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

shortest pathsdistributed algorithms

Mathematics Subject Classification ID

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

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)

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

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)