Polylog-time and near-linear work approximation scheme for undirected shortest paths

DOI10.1145/331605.331610zbMath1094.68700OpenAlexW2085630237MaRDI QIDQ4406310

Edith Cohen

Publication date: 25 June 2003

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

faster sequential algorithmsnear-linear work algorithmspolylog-time randomized algorithmsparse hop setstransitive closure bottleneckweighted undirected networks

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (17)

Thorup-Zwick emulators are universally optimal hopsets ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Transitive-Closure Spanners: A Survey ⋮ Graph spanners: a tutorial review ⋮ Unnamed Item ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time ⋮ Fast approximate shortest paths in the congested clique ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC

This page was built for publication: Polylog-time and near-linear work approximation scheme for undirected shortest paths