论文标题
计算平面图中最短路径的长度
Computing Lengths of Non-Crossing Shortest Paths in Planar Graphs
论文作者
论文摘要
鉴于平面无向图$ g $，具有非负边缘的重量和外部面上的一组$ k $终端对，在高桥等人中显示。 （Algorithmica，16，1996，pp。339-357）$ u $ u $ u $ u $ u $ u $ non-k $ non-brossing最短路径加入了$ k $ terminal对（如果存在的话），则可以在$ o（n \ log n）$ time中计算，而$ n $是$ n $ $ g $ g $ $ g $。在有限的情况下，最短路径的联合$ u $是森林，还表明它们的长度可以在同一时间绑定。我们在本文中表明，始终可以计算$ k $的最短路径的长度在线性时间内连接$ k $终端对，一旦计算出最短的路径union $ u $，也可以在$ u $中包含循环。 此外，每个最短路径$π$都可以在$ o（\ max \ {\ ell，\ ell \ log \ frac {k} {\ ell} \}）$中列出，其中$ \ ell $是$π$中的$ \ ell $。 结果，可以在一般情况下以$ O（n \ log k）$时间来求解非方向加权图的非交叉路径及其长度的问题。
Given a plane undirected graph $G$ with non-negative edge weights and a set of $k$ terminal pairs on the external face, it is shown in Takahashi et al. (Algorithmica, 16, 1996, pp. 339-357) that the union $U$ of $k$ non-crossing shortest paths joining the $k$ terminal pairs (if they exist) can be computed in $O(n\log n)$ time, where $n$ is the number of vertices of $G$. In the restricted case in which the union $U$ of the shortest paths is a forest, it is also shown that their lengths can be computed in the same time bound. We show in this paper that it is always possible to compute the lengths of $k$ non-crossing shortest paths joining the $k$ terminal pairs in linear time, once the shortest paths union $U$ has been computed, also in the case $U$ contains cycles. Moreover, each shortest path $π$ can be listed in $O(\max\{\ell, \ell \log\frac{k}{\ell} \})$, where $\ell$ is the number of edges in $π$. As a consequence, the problem of computing non-crossing shortest paths and their lengths in a plane undirected weighted graph can be solved in $O(n\log k)$ time in the general case.
