The maximum flows in bipartite dynamic networks

Abstract

In this paper, we study maximum flow algorithms for stationary bipartite dynamic networks. In a bipartite static network, the several maximum flow algorithms can be substantially improved. The basic idea in this improvement is a two arcs push rule. This idea is also extended to minimum cost flow. At the end of the paper, we present an example.