Distance Oracles for Stretch Less Than 2

DOI10.1137/1.9781611973105.38MaRDI QIDQ5741746zbMATH OpenOpenAlexFDO

Authors Rachit Agarwal, P. Brighten Godfrey

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

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximate distance oracles
• The space-stretch-time tradeoff in distance oracles
• Brief announcement: A simple stretch 2 distance oracle
• Approximating approximate distance oracles
• scientific article; zbMATH DE number 1979513
• Approximate distance oracles with improved bounds
• Approximate distance oracles with improved stretch for sparse graphs
• Approximate distance oracles with improved stretch for sparse graphs
• Approximate distance oracles for geometric spanners
• Approximate distance oracles

Cited in

(11)

• Preprocess, set, query!
• An axiomatic approach to time-dependent shortest path oracles
• The space-stretch-time tradeoff in distance oracles
• A hierarchy of lower bounds for sublinear additive spanners
• Brief announcement: A simple stretch 2 distance oracle
• Approximate distance oracles with improved stretch for sparse graphs
• Close to linear space routing schemes
• Shortest-Path Queries in Geometric Networks
• Approximate distance sensitivity oracles in subquadratic space
• On the space usage of approximate distance oracles with sub-2 stretch
• New approximate distance oracles and their applications

This page was built for publication: Distance Oracles for Stretch Less Than 2

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