Faster distributed shortest path approximations via shortcuts

DOI10.4230/LIPICS.DISC.2018.33MaRDI QIDQ5090925zbMATH OpenFDO

Authors Bernhard Haeupler, Jason Li

Publication date 21 July 2022

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

zbMATH Keywords

shortcutsshortest pathdistributed graph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Distributed algorithms (68W15)

Recommendations

• Distributed approximation algorithms for weighted shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• Improved distributed algorithms for exact shortest paths

Cites work

• scientific article; zbMATH DE number 432834 (Why is no real title available?)
• scientific article; zbMATH DE number 53482 (Why is no real title available?)
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Almost-Tight Distributed Minimum Cut Algorithms
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Distributed Strong Diameter Network Decomposition
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed approximation algorithms for weighted shortest paths
• Distributed verification and hardness of distributed approximation
• Fast distributed construction of k-dominating sets and applications
• Fast partial distance estimation and applications
• Low-congestion shortcuts without embedding
• Low-diameter graph decomposition is in NC
• Near-optimal low-congestion shortcuts on bounded parameter graphs
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Cited in

(11)

• Low-congestion shortcut and graph parameters
• scientific article; zbMATH DE number 1512693 (Why is no real title available?)
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
• A distributed algorithm for directed minimum-weight spanning tree
• scientific article; zbMATH DE number 5734726 (Why is no real title available?)
• Improved distributed algorithms for exact shortest paths

This page was built for publication: Faster distributed shortest path approximations via shortcuts

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