Single-Source Shortest Paths in the CONGEST Model with Improved Bound

DOI10.1145/3382734.3405729MaRDI QIDQ5855273zbMATH OpenOpenAlexFDO

Authors Shiri Chechik, Doron Mukhtar

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3382734.3405729

zbMATH Keywords

distributed algorithmsoverlay networkssingle-source shortest pathsbroadcast CONGEST

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Single-source shortest paths in the CONGEST model with improved bounds
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed approximation algorithms for weighted shortest paths
• Reachability and shortest paths in the broadcast CONGEST model

Cited in

(9)

• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Approximate minimum directed spanning trees under congestion
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• scientific article; zbMATH DE number 7121921 (Why is no real title available?)
• Distributed distance approximation
• Delay-constrained shortest paths: approximation algorithms and second-order cone models
• Single-source shortest paths in the CONGEST model with improved bounds
• Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
• A distributed algorithm for directed minimum-weight spanning tree

This page was built for publication: Single-Source Shortest Paths in the CONGEST Model with Improved Bound

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