Faster distributed shortest path approximations via shortcuts

DOI10.4230/LIPICS.DISC.2018.33zbMATH Open1502.68363arXiv1802.03671MaRDI QIDQ5090925FDOQ5090925

Authors: Bernhard Haeupler, Jason Li 

Publication date: 21 July 2022

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

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

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)

Cites Work

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

Cited In (11)

• Low-congestion shortcut and graph parameters
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)