Wave algorithm for maximum flow in bipartite networks

Abstract

In this paper, we develop a wave algorithm for determining a maximum ow in a bipartite network. This algorithm is a special implementation of the generic pre-flow algorithm for bipartite networks ([1]). It performs passes over active nodes. In each pass, it examines all the active nodes in nondecreasing order of their distance labels. The algorithm ends when there are no more active nodes, which means that a maximum flow was established.