Reverse Shortest Path Problem for Unit-Disk Graphs
Reverse Shortest Path Problem for Unit-Disk Graphs
复制标题
DOI：
10.1007/978-3-030-83508-8_47
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Haitao Wang;Yiming Zhao
中科院分区：
文献类型：
--
作者：
Haitao Wang;Yiming Zhao
给定平面上的点集P_n，一个关于半径的单位圆盘图是一个无向图，其顶点集为P，使得一条边连接两个点，且两点之间的欧氏距离最小。任意一条路径的长度都是该路径的边数，给定一个值和两个点，且p为0，我们考虑如下的反向最短路径问题：求最小的r，使得最短路径的长度至多为p。以前大家都知道这个问题是可以及时解决的。本文提出了一种时间算法和另一种时间算法。
Given a setPofnpoints in the plane, a unit-disk graphwith respect to a radiusris an undirected graph whose vertex set isPsuch that an edge connects two pointsif the Euclidean distance betweenpandqis at mostr. The length of any path inis the number of edges of the path. Given a valueand two pointssandtofP, we consider the followingreverse shortest path problem: finding the smallestrsuch that the shortest path length betweensandtinis at most. It was known previously that the problem can be solved intime. In this paper, we present an algorithm oftime and another algorithm oftime.