Polylog-time and near-linear work approximation scheme for undirected shortest paths
From MaRDI portal
Publication:2817594
DOI10.1145/195058.195089zbMath1344.68283OpenAlexW2082210092MaRDI QIDQ2817594
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195089
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Signed and weighted graphs (05C22)
Related Items
Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models, The geometry of graphs and some of its algorithmic applications, Low-light trees, and tight lower bounds for Euclidean spanners
