Algorismes de flux màxim en xarxes de flux

Abstract

[en] The aim of this project is to study the maximum flow problem in a flow network. It consists of finding the maximum flow capacity that any given flow network can hold, from a source node to a sink node. We will use the generic preflow-push algorithm, the FIFO preflow-push algorithm and the highest-label preflow-push algorithm. Furthermore, we will use an adaptation of the generic preflow-push specific for bipartite networks that will be used in a real life situation such as the Baseball Elimination. Finally, we would be able to analyse the direct implementation of the algorithms as well as examining the results in a simulator.