Distance Oracles for Stretch Less Than 2

DOI10.1137/1.9781611973105.38zbMath1422.68039OpenAlexW4236253639MaRDI QIDQ5741746

P. Brighten Godfrey, Rachit Agarwal

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d225de7d1f7819b5280d15492d188c1a67b3ffd3

Mathematics Subject Classification ID

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) Data structures (68P05)

Related Items

Distance oracles for time-dependent networks ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Shortest-Path Queries in Geometric Networks ⋮ Preprocess, set, query! ⋮ Close to linear space routing schemes ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ An axiomatic approach to time-dependent shortest path oracles