Shortest noncrossing paths in plane graphs
Shortest noncrossing paths in plane graphs
复制标题
平面图中的最短不相交路径
DOI：
10.1007/bf01955681
复制
发表时间：
1996
期刊：
影响因子：
1.1
通讯作者：
Takao Nishizeki
中科院分区：
文献类型：
--
作者：
Jun;H. Suzuki;Takao Nishizeki
设G是一个边长非负的无向平面图，且letk-终端对位于两个指定的面边界上。本文给出了求G中k条连接一个端点对且总长度最小的“不相交路”的算法。非交叉路径可以共享公共顶点或边，但在平面中彼此不交叉。该算法的运行时间为O（nlogn），其中Gandn中的顶点数是任意整数。
Let G be an undirected plane graph with nonnegative edge length, and letkterminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk“noncrossing paths” inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(nlogn) wherenis the number of vertices inGandkis an arbitrary integer.