More Compact Oracles for Approximate Distances in Undirected Planar Graphs

DOI10.1137/1.9781611973105.40zbMath1423.68350OpenAlexW4239159750MaRDI QIDQ5741748

Ken-ichi Kawarabayashi, Mikkel Thorup, Christian Sommer

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://doi.org/10.1137/1.9781611973105.40

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (8)

Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Efficient vertex-label distance oracles for planar graphs ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs ⋮ Unnamed Item ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs

This page was built for publication: More Compact Oracles for Approximate Distances in Undirected Planar Graphs