Wave algorithm for maximum ow in semi-bipartite networks

Abstract

In this paper we develop a new algorithm for solving the maximum flow problem in semi-bipartite networks. This algorithm is a specic implementation of the generic algorithm described in [4], obtained by performing passes through the active nodes. During such a pass, all the active nodes are examined in nonincreasing order of their exact distance labels, and their excesses are, partially or totally, moved closer to the sink node. After O(n₁²) passes, all the active node excesses are moved to the sink node or back to the source node and a maximum ow is obtained.