The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs
复制标题
圆盘图的未加权和加权反向最短路径问题
DOI：
10.48550/arxiv.2307.14663
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
Haim Kaplan;M. J. Katz;Rachel Saban;M. Sharir
研究了平面上圆盘图的逆最短路问题。在这个问题中，我们考虑任意半径平面上的一组$n$圆盘的接近图：在这个图中，如果两个圆盘之间的距离至多是某个阈值参数$r$，则它们是连通的。交图的情况是$r=0$的特例。我们给出了一个算法，在给定目标长度$k$的情况下，计算在接近图中给定的圆盘对之间至多有一条长度为$k$的路径的$r$的最小值。我们的算法运行在$O^*(n^{5/4})$随机化的预期时间内，对于所有圆盘半径相同的单位圆盘图，改进为$O^*(n^{6/5})$。我们的技术是健壮的，可以应用于问题的许多变体。一种重要的变化是加权接近图的情况，其中边被分配了等于圆盘之间或其中心之间的距离的实数权重，并且$k$被目标权重$w$替换；也就是说，我们寻找长度至多为$w$的路径。在其他变体中，我们希望优化一个不同于$r$的参数，例如磁盘半径的比例因子。问题的决策版本(确定具有给定$r$的图是否具有所需性质)的主要技术是基于BFS(对于未加权情况)和Dijkstra算法(对于加权情况)的有效实现，使用有效的数据结构来维护某些双色和几个距离函数的双色最接近对。然后，通过将所得到的决策过程与[4]的区间收缩和分叉技术的增强变体相结合来解决优化问题。
We study the reverse shortest path problem on disk graphs in the plane. In this problem we consider the proximity graph of a set of $n$ disks in the plane of arbitrary radii: In this graph two disks are connected if the distance between them is at most some threshold parameter $r$. The case of intersection graphs is a special case with $r=0$. We give an algorithm that, given a target length $k$, computes the smallest value of $r$ for which there is a path of length at most $k$ between some given pair of disks in the proximity graph. Our algorithm runs in $O^*(n^{5/4})$ randomized expected time, which improves to $O^*(n^{6/5})$ for unit disk graphs, where all the disks have the same radius. Our technique is robust and can be applied to many variants of the problem. One significant variant is the case of weighted proximity graphs, where edges are assigned real weights equal to the distance between the disks or between their centers, and $k$ is replaced by a target weight $w$; that is, we seek a path whose length is at most $w$. In other variants, we want to optimize a parameter different from $r$, such as a scale factor of the radii of the disks. The main technique for the decision version of the problem (determining whether the graph with a given $r$ has the desired property) is based on efficient implementations of BFS (for the unweighted case) and of Dijkstra's algorithm (for the weighted case), using efficient data structures for maintaining the bichromatic closest pair for certain bicliques and several distance functions. The optimization problem is then solved by combining the resulting decision procedure with enhanced variants of the interval shrinking and bifurcation technique of [4].
加权单位圆盘图中的逆向最短路径问题
DOI：
10.1007/978-3-030-96731-4_12
发表时间：
2022
期刊：
Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2012
影响因子：
--
作者：
Wang, Haitao;Zhao, Yiming
通讯作者：
Zhao, Yiming
动态广义最近对：重温 Eppstein 的技术
DOI：
10.1137/1.9781611976014.6
发表时间：
2020
期刊：
Proc. SIAM Symposium on Simplicity of Algorithms (SOSA
影响因子：
--
作者：
Chan, Timothy M.
通讯作者：
Chan, Timothy M.