A new polynomial algorithm for maximum value flow with an efficient parallel implementation

Gary R. Waissi

Naval Research Logistics (NRL), 1993, vol. 40, issue 3, 393-414

Abstract: A new algorithm is presented for finding maximal and maximum value flows in directed single‐commodity networks. Commonly algorithms developed for this problem find a maximal flow by gradually augmenting (increasing) a feasible flow to a maximal flow. In the presented algorithm, at the beginning of each step or iteration, the flow on arcs is assigned to flow capacity. This may lead to an infeasible flow violating flow conservation at some nodes. During two passes of a MAIN step, consisting of a forward pass and a backward pass, the flow is reduced on some arcs to regain feasibility. The network is then pruned by omitting saturated arcs, and the process is repeated. The parallel implementation of the algorithm applies the two main steps at the same time to the same network. The outputs of the two steps are compared and the processing continues with the higher feasible flow. The algorithm is simple, intuitive, and efficient. © 1993 John Wiley & Sons, Inc.

Date: 1993
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199304)40:33.0.CO;2-1

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:40:y:1993:i:3:p:393-414

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 ().