Using Selective Path-Doubling for Parallel Shortest-Path Computations

DOI10.1006/JAGM.1996.0813MaRDI QIDQ3125218zbMATH OpenOpenAlexFDO

Authors Edith Cohen

Publication date 19 October 1997

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

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

zbMATH Keywords

parallel shortest-paths computations

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• Polylog-time and near-linear work approximation scheme for undirected shortest paths (extended abstract)
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Δ-stepping: a parallelizable shortest path algorithm
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• scientific article; zbMATH DE number 1305103

Cited in

(9)

• Thorup-Zwick emulators are universally optimal hopsets
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• A survey of the all-pairs shortest paths problem and its variants in graphs
• Polylog-time and near-linear work approximation scheme for undirected shortest paths (extended abstract)
• scientific article; zbMATH DE number 6708314 (Why is no real title available?)
• 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

This page was built for publication: Using Selective Path-Doubling for Parallel Shortest-Path Computations

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