THE MAXIMUM FLOW PROBLEM ON THE NETWORKS – ANALYSIS AND SINTHESIS OF THE ALGORITHMS

Tatiana PAȘA Universitatea de Stat din Moldova

Abstract

In this paper, we describe generally the algorithms that solve the max-flow problem in the transport networks. We describe the basic techniques used over time, starting with the algorithm proposed by L.R. Ford and D.R. Fulkerson [1]. We also make a reference to the authors that investigate the special cases of this problem, i.e undirected graphs, bipartite or with several sources and sinks. Keywords: transportation network, maximum flow, arc capacity, residual graph, minimum cut, augmenting path, sours, destination.