An algorithmic framework for the single source shortest path problem with applications to disk graphs

DOI10.1016/j.comgeo.2022.101979zbMath1516.05210OpenAlexW4311769354MaRDI QIDQ6101843

Katharina Klost

Publication date: 20 June 2023

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2022.101979

zbMATH Keywords

shortest pathdisk graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Dynamic connectivity in disk graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• A sweepline algorithm for Voronoi diagrams
• Reverse shortest path problem in weighted unit-disk graphs
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Near-optimal algorithms for shortest paths in weighted unit-disk graphs
• Shortest paths in intersection graphs of unit disks
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
• Geometry helps in bottleneck matching and related problems

This page was built for publication: An algorithmic framework for the single source shortest path problem with applications to disk graphs