On the complexity of preflow-push algorithms for maximum-flow problems
On the complexity of preflow-push algorithms for maximum-flow problems
复制标题
最大流问题的预流推算法的复杂性
作者：
L. Tunçel
我们研究了Goldberg和Tarjan的最大流算法，并证明了最大标签实现的时间复杂度为O（n2 μ m）。我们给出了这个事实的新证明。我们将我们的证明与Cheriyan和Maheswari的早期工作进行了比较，他们表明Goldberg和Tarjan的预流推送算法的最大标签实现在O（n2 m）时间内运行。我们的证明，非饱和推送的数量是O（n2 m），不依赖于实现与当前边缘推送，因此，它是真正的一个更大的家庭的最大标签实现的预流推送算法。
We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n2√m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs inO(n2√m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n2√m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms.