| Article ID: | iaor20102863 |
| Volume: | 36 |
| Issue: | 4 |
| Start Page Number: | 397 |
| End Page Number: | 398 |
| Publication Date: | Jul 2008 |
| Journal: | Operations Research Letters |
| Authors: | Haeupler Bernhard, Tarjan Robert E |
We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg–Rao maximum flow method by a constant factor.