Shortest paths in intersection graphs of unit disks
From MaRDI portal
Publication:2344058
DOI10.1016/j.comgeo.2014.12.003zbMath1312.05041arXiv1402.4855OpenAlexW2962776480MaRDI QIDQ2344058
Publication date: 12 May 2015
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.4855
Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Signed and weighted graphs (05C22)
Related Items (17)
Two optimization problems for unit disks ⋮ Reverse shortest path problem for unit-disk graphs ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ Spanners for Directed Transmission Graphs ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ Unnamed Item ⋮ 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 ⋮ Dynamic connectivity in 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 ⋮ Reachability problems for transmission graphs ⋮ Reachability problems for transmission graphs ⋮ Unnamed Item ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
Cites Work
- On bounded leg shortest paths problems
- Unit disk graphs
- Dynamic Euclidean minimum spanning trees and extrema of binary functions
- Approximating geometric bottleneck shortest paths
- Selecting distances in the plane
- Fly Cheaply: On the Minimum Fuel Consumption Problem
- Geometry Helps in Matching
- Computing Maximally Separated Sets in the Plane
- A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
- Approximation schemes for covering and packing problems in image processing and VLSI
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- An Expander-Based Approach to Geometric Optimization
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- Testing bipartiteness of geometric intersection graphs
- Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications
- Geometry helps in bottleneck matching and related problems
This page was built for publication: Shortest paths in intersection graphs of unit disks
