A NEW APPROACH TO THE MAXIMUM-FLOW PROBLEM
A NEW APPROACH TO THE MAXIMUM-FLOW PROBLEM
复制标题
DOI：
10.1145/48014.61051
复制
发表时间：
1988-10-01
影响因子：
2.5
通讯作者：
TARJAN, RE
中科院分区：
文献类型：
--
作者：
GOLDBERG, AV;TARJAN, RE
所有以前已知的有效最大流算法都是通过寻找扩充路径来工作的，或者一次一条路径（如原始的福特和Fulkerson算法），或者一次找到所有最短长度的扩充路径（使用Dinic的分层网络方法）。介绍了一种基于Karzanov预流概念的替代方法。预流类似于流，不同之处在于允许流入顶点的总量超过流出的总量。该方法在原始网络中保持预流，并将局部流多余部分沿估计为最短路径的路径沿着推向信宿。该算法及其分析简单、直观，而且算法运行速度与稠密图上的任何已知方法一样快，在n-顶点图上达到O（n3）时间界。通过结合Sleator和Tarjan的动态树数据结构，我们得到了一个在n-顶点，m-边图上运行时间为O（nmlog（n2/m））的算法.对于任何图形密度，这与任何已知方法一样快，并且在中等密度的图形上更快。该算法还承认有效的分布式和并行实现。在n个处理器和O（m）空间上得到了一个O（n2 logn）时间的并行实现。这个时间界限与Shiloach-Vishkin算法的时间界限相匹配，Shiloach-Vishkin算法也使用n个处理器，但需要O（n2）空间。
All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on thepreflowconcept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving anO(n3) time bound on ann-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running inO(nmlog(n2/m)) time on ann-vertex,m-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running inO(n2logn) time usingnprocessors andO(m) space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also usesnprocessors but requiresO(n2) space.