Reverse Shortest Path Problem in Weighted Unit-Disk Graphs
Reverse Shortest Path Problem in Weighted Unit-Disk Graphs
复制标题
加权单位圆盘图中的逆向最短路径问题
DOI：
10.1007/978-3-030-96731-4_12
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Zhao, Yiming
中科院分区：
文献类型：
--
作者：
Wang, Haitao;Zhao, Yiming
给定平面上的点集P_n，关于参数的单位圆盘图是一个无向图，它的顶点集是P，使得一条边连接两个点，如果两个点之间的（欧几里德）距离是最大的（在未加权的情况下，边的权是1，在加权的情况下，是两个点之间的距离）。给定一个值和两个点，并tofP，我们考虑如下的反向最短路问题：计算最小的，使得最短路长度最多为之间。本文研究了加权情况，提出了一种时间算法.我们还考虑了两点的距离是由themetric测量的问题的版本，我们解决了未加权和加权的情况下的时间问题。
Given a setPofnpoints in the plane, a unit-disk graphwith respect to a parameterris an undirected graph whose vertex set isPsuch that an edge connects two pointsif the (Euclidean) distance betweenpandqis at mostr(the weight of the edge is 1 in the unweighted case and is the distance betweenpandqin the weighted case). Given a valueand two pointssandtofP, we consider the followingreverse shortest path problem: Compute the smallestrsuch that the shortest path length betweensandtinis at most. In this paper, we study the weighted case and present antime algorithm. We also consider theversion of the problem where the distance of two points is measured by themetric; we solve the problem intime for both the unweighted and weighted cases.