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: | Gonzlez-Martn Carlos, Sedno-Noda Antonio, Alonso Sergio |
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 β =