A Randomized Parallel Algorithm for Single-Source Shortest Paths
From MaRDI portal
Publication:4372999
DOI10.1006/JAGM.1997.0888zbMATH Open0887.68047OpenAlexW2056496054MaRDI QIDQ4372999FDOQ4372999
Authors: Philip N. Klein, Sairam Subramanian 
Publication date: 18 December 1997
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/374f9f0f84c939e28a26aa5eb7370ecc12d658d1
Recommendations
Cited In (27)
- Title not available (Why is that?)
- Computational Science – ICCS 2005
- Hopsets with constant hopbound, and applications to approximate shortest paths
- Title not available (Why is that?)
- Thorup-Zwick emulators are universally optimal hopsets
- Title not available (Why is that?)
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Undirected single-source shortest paths with positive integer weights in linear time
- Title not available (Why is that?)
- A hierarchy of lower bounds for sublinear additive spanners
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding real-valued single-source shortest paths in \(o(n^3)\) expected time
- Nearly work-efficient parallel algorithm for digraph reachability
- Δ-stepping: a parallelizable shortest path algorithm
- Polylog-time and near-linear work approximation scheme for undirected shortest paths (extended abstract)
- Single-source shortest paths in the CONGEST model with improved bounds
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- Distributed planar reachability in nearly optimal time
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- Improved processor bounds for parallel algorithms for weighted directed graphs
- A mechanism design approach for multi-party machine learning
- Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
- A simple parallel algorithm for the single-source shortest path problem on planar digraphs
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Title not available (Why is that?)
This page was built for publication: A Randomized Parallel Algorithm for Single-Source Shortest Paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4372999)
