Time–Work Tradeoffs of the Single-Source Shortest Paths Problem

DOI10.1006/JAGM.1998.0968MaRDI QIDQ4228283zbMATH OpenOpenAlexFDO

Authors Hanmao Shi, Thomas H. Spencer

Publication date 21 June 1999

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1998.0968

zbMATH Keywords

single-source shortest path problem

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• Time-work tradeoffs for parallel algorithms
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• A simple parallel algorithm for the single-source shortest path problem on planar digraphs
• scientific article; zbMATH DE number 1186513
• scientific article; zbMATH DE number 934538

Cited in

(13)

• Thorup-Zwick emulators are universally optimal hopsets
• Fast approximate shortest paths in the congested clique
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Simpler computation of single-source shortest paths in linear average time
• Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
• Time-work tradeoffs for parallel algorithms
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• A hierarchy of lower bounds for sublinear additive spanners
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
• Hopsets with constant hopbound, and applications to approximate shortest paths
• scientific article; zbMATH DE number 7121921 (Why is no real title available?)
• Computing single source shortest paths using single-objective fitness

This page was built for publication: Time–Work Tradeoffs of the Single-Source Shortest Paths Problem

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