Shortest-Path Queries in Geometric Networks

DOI10.4230/LIPICS.ISAAC.2020.52MaRDI QIDQ6065461zbMATH OpenOpenAlexFDO

Authors Eunjin Oh

Publication date 14 November 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/13396/pdf/LIPIcs-ISAAC-2020-52.pdf/

zbMATH Keywords

data structureEuclidean spannershortest path

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• Almost optimal distance oracles for planar graphs
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Approximate distance oracles
• Approximate distance oracles for geometric spanners
• Better tradeoffs for exact distance oracles in planar graphs
• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Distance oracles beyond the Thorup-Zwick bound
• Distance Oracles for Stretch Less Than 2
• Fast Algorithms for Finding Nearest Common Ancestors
• Faster approximate diameter and distance oracles in planar graphs
• Geometric Spanner Networks
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimal Euclidean Spanners
• Optimal shortest path queries in a simple polygon
• Real-world applications of shortest path algorithms
• Shortest-path queries in static networks
• STACS 2005
• The level ancestor problem simplified
• Well-separated pair decomposition for the unit-disk graph metric and its applications

Cited in

(11)

• Shortest path to a segment and quickest visibility queries
• Approximate Shortest Path Queries Using Voronoi Duals
• Querying Approximate Shortest Paths in Anisotropic Regions
• Drawing Shortest Paths in Geodetic Graphs
• Drawing Shortest Paths in Geodetic Graphs
• Shortest-path queries in static networks
• Shortest paths, single origin‐destination network design, and associated polyhedra
• Geometric k Shortest Paths
• Reachability problems for transmission graphs
• Reachability problems for transmission graphs
• Shortest beer path queries in outerplanar graphs

This page was built for publication: Shortest-Path Queries in Geometric Networks

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