Shortest-Path Queries in Geometric Networks

DOI10.4230/lipics.isaac.2020.52OpenAlexW3117971186MaRDI QIDQ6065461

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

shortest pathdata structureEuclidean spanner

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (2)

Reachability problems for transmission graphs ⋮ Reachability problems for transmission graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The level ancestor problem simplified
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Optimal shortest path queries in a simple polygon
• Faster approximate diameter and distance oracles in planar graphs
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
• Optimal Euclidean Spanners
• Fast Algorithms for Finding Nearest Common Ancestors
• Geometric Spanner Networks
• Approximate distance oracles
• Well-separated pair decomposition for the unit-disk graph metric and its applications
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• Approximate distance oracles for geometric spanners
• Shortest-path queries in static networks
• Almost optimal distance oracles for planar graphs
• Distance Oracles beyond the Thorup--Zwick Bound
• STACS 2005
• Distance Oracles for Stretch Less Than 2

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