Distance‐directed augmenting path algorithms for maximum flow and parametric maximum flow problems

Ravindra K. Ahuja and James B. Orlin

Naval Research Logistics (NRL), 1991, vol. 38, issue 3, 413-430

Abstract: Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in recent years, new distance‐directed algorithms have been suggested that do not construct layered networks but instead maintain a distance label with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this article we develop two distance‐directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n2m) time on networks with n nodes and m arcs. We also point out the relationship between the distance labels and layered networks. Using a scaling technique, we improve the complexity of our distance‐directed algorithms to O(nm log U), where U denotes the largest arc capacity. We also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problems.

Date: 1991
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199106)38:33.0.CO;2-J

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:38:y:1991:i:3:p:413-430

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().