Maximum Flow in Planar Networks
Maximum Flow in Planar Networks
复制标题
平面网络中的最大流
DOI：
10.1137/0208012
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
Y. Shiloach
中科院分区：
文献类型：
--
作者：
A. Itai;Y. Shiloach
提出了在平面网络中寻找最大流的有效算法。这些算法利用了平面性，并且优于迄今为止最有效的算法。如果源端和终端在同一个面上，改进了Berge的算法，其时间复杂度降低到$O(n\log n)$。在一般情况下，对于给定的 $D > 0$，如果存在价值 D 的流，则找到该流；否则，表明不存在该流。该算法需要 $O(n^2 \log n)$ 时间。如果网络是无向的，则可以在 $O(n^2 \log n)$ 时间内找到最小割。所有算法都需要 $O(n)$ 空间。
Efficient algorithms for finding maximum flow in planar networks are presented. These algorithms take advantage of the planarity and are superior to the most efficient algorithms to date. If the source and the terminal are on the same face, an algorithm of Berge is improved and its time complexity is reduced to $O(n\log n)$. In the general case, for a given $D > 0$ a flow of value D is found if one exists; otherwise, it is indicated that no such flow exists. This algorithm requires $O(n^2 \log n)$ time. If the network is undirected a minimum cut may be found in $O(n^2 \log n)$ time. All algorithms require $O(n)$ space.