Near-optimal algorithms for shortest paths in weighted unit-disk graphs

DOI10.1007/s00454-020-00219-7zbMath1466.05202arXiv1903.05255OpenAlexW3037400150MaRDI QIDQ2223616

Yanyan Li

Publication date: 29 January 2021

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.05255

zbMATH Keywords

single-source shortest pathsgeometric graph algorithmsweighted unit-disk graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Reverse shortest path problem for unit-disk graphs ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ On reverse shortest paths in geometric proximity graphs ⋮ An algorithmic framework for the single source shortest path problem with applications to disk graphs ⋮ Reachability problems for transmission graphs ⋮ Reachability problems for transmission graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On bounded leg shortest paths problems
• A sweepline algorithm for Voronoi diagrams
• Unit disk graphs
• Decomposable searching problems
• Shortest paths in intersection graphs of unit disks
• All-pairs shortest paths in geometric intersection graphs
• Optimal Point Location in a Monotone Subdivision
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Fine-grained complexity analysis of two classic TSP variants
• A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
• Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications

This page was built for publication: Near-optimal algorithms for shortest paths in weighted unit-disk graphs