El problema del flujo máximo: Teoría, algoritmos y aplicaciones

Abstract

[ES] A lo largo de esta memoria estudiaremos en profundidad el problema de flujo máximo y veremos algunas de sus aplicaciones prácticas. Este estudio incluirá resultados teóricos que relacionan este problema con otros ya conocidos, como el teorema max-flow min-cut, y se presentará la familia de algoritmos de trayectorias aumentadas, diseñada para la resolución del problema.

[EN] In this paper we will study the maximum flow problem and we will show some of its practical applications. We will include theorical results to relate this problem with other well known problems, like max-flow min-cut theorem. Moreover, the family of augmenting path algorithms, designed to solve this problem, will be presented.