Approximate distance oracles for geometric spanners

DOI10.1145/1328911.1328921MaRDI QIDQ4962702zbMATH OpenOpenAlexFDO

Authors Joachim Gudmundsson, Giri Narasimhan, Christos Levcopoulos, Michiel Smid

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1328911.1328921

zbMATH Keywords

approximation algorithmcomputational geometrygeometric graphsshortest pathsspanners

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 2119744
• scientific article; zbMATH DE number 1979513
• Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
• Algorithms and Computation
• Approximate distance oracles

Cited in

(27)

• Approximating geometric bottleneck shortest paths
• Graph spanners: a tutorial review
• scientific article; zbMATH DE number 1809600 (Why is no real title available?)
• Compact Oracles for Approximate Distances Around Obstacles in the Plane
• scientific article; zbMATH DE number 1962800 (Why is no real title available?)
• scientific article; zbMATH DE number 1979513 (Why is no real title available?)
• scientific article; zbMATH DE number 1830742 (Why is no real title available?)
• scientific article; zbMATH DE number 2119744 (Why is no real title available?)
• Euclidean Steiner spanners: light and sparse
• Truly Optimal Euclidean Spanners
• Fast, precise and dynamic distance queries
• Distance Oracles for Stretch Less Than 2
• Light Euclidean Spanners with Steiner Points
• Reachability problems for transmission graphs
• Reachability problems for transmission graphs
• Lower bounds for computing geometric spanners and approximate shortest paths
• Shortest-Path Queries in Geometric Networks
• Online Spanners in Metric Spaces
• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
• Truly optimal Euclidean spanners
• Online spanners in metric spaces
• Online Euclidean spanners
• On euclidean Steiner (1+)-spanners
• Light Euclidean Steiner spanners in the plane
• A WSPD, separator and small tree cover for c-packed graphs
• Light spanners with small hop-diameter
• Approximate distance oracles for graphs with dense clusters

This page was built for publication: Approximate distance oracles for geometric spanners

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