Simple Generalized Maximum Flow Algorithms
Simple Generalized Maximum Flow Algorithms
复制标题
简单广义最大流算法
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Kevin Wayne
中科院分区：
文献类型：
--
作者：
É. Tardos;Kevin Wayne
对于广义最大流问题，我们引入了一种增益缩放技术。利用这一技巧，我们给出了三种简单直观的多项式时间组合算法。Truemper的增广路径算法是解决该问题的最简单的组合算法之一，但运行时间为指数时间。我们的第一个算法是Truemper算法的多项式时间变量。我们的第二个算法是Goldberg和Tarjan的预流推送算法的改编。这是广义网络中第一个多项式时间预流推算法。我们的第三个算法是Fat-Path容量缩放算法的变体。它比Radzik的变种简单得多，并且与问题的最著名的复杂性相匹配。我们讨论了在实施方面的实际改进。
We introduce a gain-scaling technique for the generalized maximum flow problem. Using this technique, we present three simple and intuitive polynomial-time combinatorial algorithms for the problem. Truemper’s augmenting path algorithm is one of the simplest combi- natorial algorithms for the problem, but runs in exponential-time. Our first algorithm is a polynomial-time variant of Truemper’s algorithm. Our second algorithm is an adaption of Goldberg and Tarjan’s preflow- push algorithm. It is the first polynomial-time preflow-push algorithm in generalized networks. Our third algorithm is a variant of the Fat-Path capacity-scaling algorithm. It is much simpler than Radzik’s variant and matches the best known complexity for the problem. We discuss practical improvements in implementation.