Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs.

DOI10.4230/LIPIcs.SoCG.2019.60OpenAlexW2922095319MaRDI QIDQ5088993

No author found.

Publication date: 18 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.60

zbMATH Keywords

single-source shortest pathsgeometric graph algorithmsweighted unit-disk graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications

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
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Fine-grained complexity analysis of two classic TSP variants
• 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.