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

DOI10.1007/S00454-020-00219-7MaRDI QIDQ2223616zbMATH OpenOpenAlexFDO

Authors 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, https://drops.dagstuhl.de/opus/volltexte/2019/10464/

zbMATH Keywords

geometric graph algorithmssingle-source shortest pathsweighted unit-disk graphs

Mathematics Subject Classification ID

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

Abstract: We revisit a classical graph-theoretic problem, the extit{single-source shortest-path} (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in $O(nlo{g}^{2}n)$ time using linear space, where $n$ is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejv{c}iv{c} [CGTA'15] which uses $O(n^{1+delta})$ time and $O(n^{1+delta})$ space (for any small constant $delta>0$) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses $O(nlo{g}^{12+o(1)}n)$ expected time and $O(nlo{g}^{3}n)$ space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with $k$ operations (i.e., insertions and queries) can be solved in $f(k)$ time, then the SSSP problem in weighted unit-disk graphs can be solved in $O(nlogn+f(n))$ time. Using the same framework with some new ideas, we also obtain a $(1+varepsilon)$-approximate algorithm for the problem, using $O(nlogn+nlo{g}^2(1/varepsilon))$ time and linear space. This improves the previous $(1+varepsilon)$-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses $O((1/varepsilon{)}^{2}nlogn)$ time and $O((1/varepsilon{)}^{2}n)$ space. More specifically, we show that if the 2D offline insertion-only weighted nearest-neighbor problem with $k_1$ operations in which at most $k_2$ operations are insertions can be solved in $f(k_1,k_2)$ time, then the $(1+varepsilon)$-approximate SSSP problem in weighted unit-disk graphs can be solved in $O(nlogn+f(n,O(varepsilo{n}^{-2})))$ time. Because of the $Omega(nlogn)$-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.

Recommendations

• Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs.
• Approximate shortest paths and distance oracles in weighted unit-disk graphs
• scientific article; zbMATH DE number 7236428
• An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs
• Approximate shortest paths in weighted graphs
• Graph-Theoretic Concepts in Computer Science
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• An algorithmic framework for the single source shortest path problem with applications to disk graphs
• Reverse shortest path problem in weighted unit-disk graphs
• scientific article; zbMATH DE number 6861957

Cites work

• A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
• A sweepline algorithm for Voronoi diagrams
• All-pairs shortest paths in geometric intersection graphs
• Decomposable searching problems
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Fine-grained complexity analysis of two classic TSP variants
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• scientific article; zbMATH DE number 6861957 (Why is no real title available?)
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• On bounded leg shortest paths problems
• Optimal Point Location in a Monotone Subdivision
• Shortest paths in intersection graphs of unit disks
• Unit disk graphs
• Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications

Cited in

(27)

• Reverse shortest path problem in weighted unit-disk graphs
• Shortest paths in intersection graphs of unit disks
• An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs
• Approximate shortest paths and distance oracles in weighted unit-disk graphs
• scientific article; zbMATH DE number 6861957 (Why is no real title available?)
• Simple heuristics for unit disk graphs
• Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs.
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• Reachability problems for transmission graphs
• Reachability problems for transmission graphs
• ETH-Tight Algorithms for Long Path and Cycle on 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
• An improved algorithm for shortest paths in weighted unit-disk graphs
• Computing the minimum bottleneck moving spanning tree
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Improved algorithms for distance selection and related problems
• Sublinear average-case shortest paths in weighted unit-disk graphs
• Segment proximity graphs and nearest neighbor queries amid disjoint segments
• Near-linear algorithms for visibility graphs over a 1.5-dimensional terrain
• Dynamic unit-disk range reporting
• Segment proximity graphs and nearest neighbor queries amid disjoint segments
• Single-source shortest path problem in weighted disk graphs
• Faster algorithms for reverse shortest path in unit-disk graphs and related geometric optimization problems: improving the shrink-and-bifurcate technique
• Computing maximum cliques in unit disk graphs
• An optimal algorithm for shortest paths in unweighted disk graphs
• Reverse shortest path problem for unit-disk graphs

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

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