A generalization of the scaling max-flow algorithm

A generalization of the scaling max-flow algorithm

0.00 Avg rating0 Votes
Article ID: iaor2005714
Country: United Kingdom
Volume: 31
Issue: 13
Start Page Number: 2183
End Page Number: 2198
Publication Date: Nov 2004
Journal: Computers and Operations Research
Authors: , ,
Abstract:

In this paper, we generalize the capacity-scaling techniques in the design of algorithms for the maximum flow problem. Since all previous scaling max-flow algorithms use only one scale factor of value 2, we propose introducing a double capacity-scaling to improve and generalize them. The first capacity scaling has a variable scale factor β and the second uses the value 2. We show that, for different values of the scale factor β, both the classical scaling algorithm (with β = U) and the two-phase double scaling-capacity max-flow algorithm (with β = 2) can be obtained. Moreover, theoretical complexities based on the worst-case analysis can be built depending on the values of β. In addition, a unique and simple implementation of the generalized method is possible and several strategies to improve its practical behavior can be incorporated. The paper finishes with a computational experiment that shows that the running time of capacity-sealing algorithms decreases as β increases.

Reviews

Required fields are marked *. Your email address will not be published.