Minimum s-t Cut of a Planar Undirected Network in O(n log2(n)) Time
Minimum s-t Cut of a Planar Undirected Network in O(n log2(n)) Time
复制标题
O(n log2(n)) 时间内平面无向网络的最小 s-t 割
DOI：
--
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
J. Reif
中科院分区：
文献类型：
--
作者：
J. Reif
设N是一个平面无向网络，具有不同的顶点s，t，总共n个顶点，每个边用集合L中的正真实的（边的成本）标记。本文提出了一种计算N的最小（代价）s-t割的算法。对于一般的L，这个算法的时间复杂度为O（nlog ^2（n））$。对于L只包含整数$ leqq n^{O（1）} $的情况，算法运行时间为$O（nlog（n）log log（n））$。我们的算法还构造了平面图的最小s-t割（即，$O（nlog（n））$的时间复杂度。我们的算法也可以用于计算一般无向平面网络的最小割。计算平面无向网络的最小s-t割的最快先前算法（Itai和Shiloach [SIAM J. Comput.，8（1979），pp.时间复杂度为O（n^2 log（n））; s-t割是他们算法计算最大流的副产品。平面图的最小s-t切割的最佳前一个时间界（Cheston，Probert和Saxton [报告，Dept.股份有限
Let N be a planar undirected network with distinguished vertices s, t, a total of n vertices, and each edge labeled with a positive real (the edge’s cost) from a set L. This paper presents an algorithm for computing a minimum (cost) s-t cut of N. For general L, this algorithm runs in time $O(nlog ^2 (n))$. For the case when L contains only integers$ leqq n^{O(1)} $, the algorithm runs in time $O(nlog (n)log log (n))$. Our algorithm also constructs a minimum s-t cut of a planar graph (i.e., for the case $L = { 1} $) in time $O(nlog (n))$. Our algorithm can also be used to compute a minimum cut for a general undirected planar network.The fastest previous algorithm for computing a minimum s-t cut of a planar undirected network (Itai and Shiloach [SIAM J. Comput., 8 (1979), pp. 135–150]) has time $O(n^2 log (n))$; the s-t cut is a byproduct of the maximum flow computed by their algorithm. The best previous time bound for minimum s-t cut of a planar graph (Cheston, Probert and Saxton [report, Dept. Co...