Distance Oracles for Sparse Graphs

DOI10.1109/FOCS.2009.27MaRDI QIDQ5171228zbMATH OpenFDO

Authors C. Sommer, Elad Verbin, Wei Yu

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2009.27

Mathematics Subject Classification ID

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

Cited in

(16)

• An introduction to the Ribe program
• Ultrametric subsets with large Hausdorff dimension
• Preprocess, set, query!
• An axiomatic approach to time-dependent shortest path oracles
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Distance oracles for vertex-labeled graphs
• On approximate distance labels and routing schemes with affine stretch
• Efficient oracles and routing schemes for replacement paths
• A hierarchy of lower bounds for sublinear additive spanners
• Shortest-path queries in static networks
• Exact distance oracles for planar graphs
• Approximate distance oracles with improved stretch for sparse graphs
• Close to linear space routing schemes
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Almost optimal exact distance oracles for planar graphs
• Worst-case to expander-case reductions: derandomized and generalized

This page was built for publication: Distance Oracles for Sparse Graphs

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