FIFO preflow algorithm for maximum flow in semi-bipartite networks

Abstract

In this paper, we develop a special implementation of the generic algorithm for determining a maximum flow in a semi-bipartite network introduced in [3]. This generic algorithm allows only nodes in N1 to be active. For this reason, it performs pushes on individual arcs having both endpoints in N1 or admissible paths of length 2 whose starting and ending nodes are both contained in N1. Because it is a generic algorithm, it doesn't specify any rule for selecting active nodes. In this paper, we will impose the FIFO rule for the active nodes selection and we will obtain a specic implementation of the generic algorithm for maximum flow in semi-bipartite networks, which has a better running time than the generic algorithm.