Analysis of Preflow Push Algorithms for Maximum Network Flow
Analysis of Preflow Push Algorithms for Maximum Network Flow
复制标题
最大网络流量的Preflow Push算法分析
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
S. Maheshwari
中科院分区：
文献类型：
--
作者：
J. Cheriyan;S. Maheshwari
我们研究了 Goldberg 和 Tarjan 最近引入的一类预流推送算法，用于解决加权有向图 G(V,E) 上的最大网络流问题。我们将 Goldberg 和 Tarjanis 最大距离预流推送算法的 O(n3) 时间界限改进为 O(n2√m)，并通过构建参数化的最坏情况网络表明该界限是严格的。然后，我们开发了最大过量预流推送算法，并证明它实现了 O(n2√m) 推送的界限。在此基础上，我们为同步分布式计算模型开发了最大网络流算法，最多使用 O(n2√m) 条消息和 O(n2) 时间，从而改进了该模型的先前已知最佳算法。
We study the class of preflow push algorithms recently introduced by Goldberg and Tarjan for solving the maximum network flow problem on a weighted digraph G(V,E). We improve Goldberg and Tarjanis O(n3) time bound for the maximum distance preflow push algorithm to O(n2√m) and show that this bound is tight by constructing a parametrized worst case network. We then develop the maximal excess preflow push algorithm and show that it achieves a bound of O(n2√m) pushes. Based on this we develop a maximum network flow algorithm for the synchronous distributed model of computation that uses at most O(n2√m) messages and O(n2) time, thereby improving upon the best previously known algorithms for this model.