A generic preflow algorithm for maximum flow in semibipartite networks

Abstract

In this paper, we develop a generic algorithm for determining the maximum flow in a semi-bipartite network. This algorithm allows only nodes in N₁ to be active. For this reason, it performs pushes on individual arcs having both endpoints in N₁ or admissible paths of length 2 whose starting and ending nodes are both contained in N₁. The running time of this algorithm is O(n²₁m).