Algorithms for finding internally disjoint paths in a planar graph
Algorithms for finding internally disjoint paths in a planar graph
复制标题
在平面图中查找内部不相交路径的算法
DOI：
10.1002/ecjc.4430721006
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
Takao Nishizeki
中科院分区：
文献类型：
--
作者：
H. Suzuki;Takehiro Akama;Takao Nishizeki
给出了平面图中求顶点不交树和内部不交路的三个有效算法。给定一个平面图G和由外部边界上的终端组成的网络，第一个算法找到顶点不相交的树，每个树将网络的所有终端互连。第二个算法确定平面图G中两个指定顶点之间内部不交路的最大数目k。第三种算法实际上找到了这k条路径。第一个算法的时间复杂度为O（n），第二个和第三个算法的时间复杂度为O（nlogn）。这里n是给定图G的顶点数。
Three efficient algorithms for finding vertex-disjoint trees and internally disjoint paths in a planar graph are presented. Given a planar graph G and nets consisting of terminals lying on the external boundary, the first algorithm finds vertex-disjoint trees, each of which interconnects all the terminals of a net. the second algorithm determines the maximum number k of internally disjoint paths between two specified vertices in the planar graph G. the third algorithm really finds these k paths. the time complexity of the first algorithm is O(n), those of the second and third are o(n log n). Here n is the number of vertices of the given graph G.