Fast and Compact Oracles for Approximate Distances in Planar Graphs

DOI10.1007/978-3-540-75520-3_58MaRDI QIDQ3527255zbMATH OpenOpenAlexFDO

Authors Laurent Flindt Muller, Martin Zachariasen

Publication date 25 September 2008

Published in Algorithms – ESA 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75520-3_58

Mathematics Subject Classification ID

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

Recommendations

• Faster approximate diameter and distance oracles in planar graphs
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• More compact oracles for approximate distances in undirected planar graphs
• Approximate distance oracles for planar graphs with improved query time-space tradeoff
• Almost optimal distance oracles for planar graphs
• Exact distance oracles for planar graphs

Cited in

(14)

• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Compact Oracles for Approximate Distances Around Obstacles in the Plane
• Engineering Route Planning Algorithms
• scientific article; zbMATH DE number 2119743 (Why is no real title available?)
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Shortest-path queries in static networks
• Almost optimal distance oracles for planar graphs
• An I/O-efficient distance oracle for evolving real-world graphs
• A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
• Compact oracles for reachability and approximate distances in planar digraphs
• scientific article; zbMATH DE number 6469155 (Why is no real title available?)
• More compact oracles for approximate distances in undirected planar graphs
• An efficient oracle for counting shortest paths in planar graphs

This page was built for publication: Fast and Compact Oracles for Approximate Distances in Planar Graphs

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