Computing oriented spanners and their dilation

DOI10.4230/LIPICS.SOCG.2025.27MaRDI QIDQ7312671zbMATH OpenFDO

Authors Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, Sampson Wong

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2025.27

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A survey of the all-pairs shortest paths problem and its variants in graphs
• A Theorem on Boolean Matrices
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Classes of graphs which approximate the complete Euclidean graph
• Computing geometric minimum-dilation graphs is NP-hard
• Computing the shortest path: A^ search meets graph theory
• Fast 2-approximate all-pairs shortest paths
• Faster approximate all pairs shortest paths
• Geometric Spanner Networks
• On plane geometric spanners: a survey and open problems
• On range searching with semialgebraic sets
• Optimal partition trees
• Oriented spanners
• Planar Formulae and Their Uses
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Subcubic equivalences between path, matrix, and triangle problems

This page was built for publication: Computing oriented spanners and their dilation

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