Distributed exact shortest paths in sublinear time

DOI10.1145/3055399.3055452MaRDI QIDQ6829662zbMATH OpenFDO

Authors Michael Elkin

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathsdistributed algorithmssublinear time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distributed algorithms (68W15)

Cited in

(3)

• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Distributed distance approximation
• New algorithms and lower bounds for streaming tournaments

This page was built for publication: Distributed exact shortest paths in sublinear time

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