Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff

DOI10.1137/1.9781611974331.ch26zbMath1411.68090arXiv1601.00839OpenAlexW2952050889MaRDI QIDQ4575603

Christian Wulff-Nilsen

Publication date: 16 July 2018

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

Full work available at URL: https://arxiv.org/abs/1601.00839

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Approximation algorithms (68W25)

Related Items

Distance oracles for time-dependent networks, Unnamed Item, Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Analysis of the Period Recovery Error Bound, Analysis of farthest point sampling for approximating geodesics in a graph, Faster approximate diameter and distance oracles in planar graphs, Efficient dynamic approximate distance oracles for vertex-labeled planar graphs, Close to linear space routing schemes, An efficient oracle for counting shortest paths in planar graphs, Single-source shortest paths and strong connectivity in dynamic planar graphs, An efficient oracle for counting shortest paths in planar graphs