Space-efficient path-reporting approximate distance oracles
From MaRDI portal
Publication:517013
DOI10.1016/j.tcs.2016.07.038zbMath1359.05121arXiv1410.0768OpenAlexW2963557505MaRDI QIDQ517013
Ofer Neiman, Michael Elkin, Christian Wulff-Nilsen
Publication date: 16 March 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.0768
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Strong-diameter decompositions of minor free graphs
- Ramsey partitions and proximity data structures
- Distance-dependent distributed directories
- Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
- Improved routing strategies with succinct tables
- Geometric Spanner Networks
- Approximate distance oracles
- A Separator Theorem for Planar Graphs
- Routing with Polynomial Communication-Space Trade-Off
- Online tracking of mobile users
- Distributed Computing: A Locality-Sensitive Approach
- Compact routing schemes with low stretch factor
- Proximity-preserving labeling schemes
- Compact name-independent routing with minimum stretch
- Compact routing schemes with improved stretch
- Object location using path separators
- Excluded minors, network decomposition, and multicommodity flow
- Cops, robbers, and threatening skeletons
- Approximate distance oracles with constant query time
- A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
- Improved sparse covers for graphs excluding a fixed minor
- Compact oracles for reachability and approximate distances in planar digraphs
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Approximate Distance Oracles with Improved Query Time
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
