Massively parallel algorithms for approximate shortest paths

DOI10.1007/S00446-025-00482-YMaRDI QIDQ6954065zbMATH OpenFDO

Authors Michal Dory, Shaked Matar

Publication date 24 July 2025

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00446-025-00482-Y

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cites work

• \((1+\varepsilon)\)-approximate shortest paths in dynamic streams
• (1 + εΒ) -spanner constructions for general graphs
• A deterministic algorithm for the MST problem in constant rounds of congested clique
• A hierarchy of lower bounds for sublinear additive spanners
• Approximate distance oracles
• Communication steps for parallel query processing
• Constant-Round Spanners and Shortest Paths in Congested Clique and MPC
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Efficient algorithms for constructing very sparse spanners and emulators
• Exponentially faster massively parallel maximal matching
• Exponentially Faster Shortest Paths in the Congested Clique
• Faster parallel algorithm for approximate shortest path
• Having hope in hops: new spanners, preservers and lower bounds for hopsets
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• scientific article; zbMATH DE number 7788448 (Why is no real title available?)
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Massively Parallel Algorithms for Minimum Cut
• Massively Parallel Computation in a Heterogeneous Regime
• Massively Parallel Computation of Matching and MIS in Sparse Graphs
• Near-additive spanners and near-exact hopsets, a unified view
• Near-additive spanners in low polynomial deterministic CONGEST time
• Parallel algorithms for geometric graph problems
• Parallel approximate undirected shortest paths via low hop emulators
• Round compression for parallel matching algorithms
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Sorting, searching, and simulation in the MapReduce framework
• Spanners and emulators with sublinear distance errors
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• Ultra-Sparse Near-Additive Emulators

This page was built for publication: Massively parallel algorithms for approximate shortest paths

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