Maximum flows in bipartite dynamic networks

Abstract

In this paper, we study the maximum flow in a bipartite dynamic network and make a synthesis of the papers [17], [18], [19], [20]. We solve this problem by a dynamic approach and a static approach. In a bipartite static network, the several maximum algorithms can be substantially improved. The basic idea in these improvements is a two arcs push rule in the case of maximum algorithms. For these problems we give examples.