Algoritmos de flujo y su implementación

Abstract

[EN] The aim of the project is to survey existing state-of-the-art flow algorithms, and implement them in a conventional programming language. Moreover, design improvements and new solutions will be explored, based on the acquired knowledge.

Flow problems appear in flow networks, that are directed graphs where each edge has an associated maximum capacity. A classical problem is to find how much flow can be pushed from a particular source vertex to a sink vertex, given the capacity restrictions. Finding the maximum flow is interesting in engineering problems that can be modeled with a flow network, like transport problems in traffic networks or electrical networks. Furthermore, the maximum flow problem can also be used to find maximum matchings in bipartite graphs, with a plethora of applications.

There exist several algorithms to solve the maximum flow problem efficiently, that have different computational complexity depending on the properties of the graph that are applied on. Their differences will be studied, and their efficient implementation, as well as possible improvements.

[ES] El objetivo del trabajo es hacer un estudio recopilatorio de los algoritmos de flujos más punteros y realizar una implementación de ellos en un lenguaje de programación convencional. También se explorarán posibles mejoras de diseño y nuevas soluciones, basadas en el conocimiento adquirido.

Los problemas de flujo aparecen en redes de flujo, que son grafos dirigidos donde cada arista tiene asociada una capacidad máxima. Un problema clásico es encontrar cuánto flujo se puede transportar desde un vértice fuente hasta un vértice sumidero dados, teniendo en cuenta las restricciones de capacidad. Encontrar el flujo máximo es interesante en problemas de ingenería que se puedan modelar con una red de flujo, como por ejemplo pueden ser problemas de transporte en redes de carreteras o en redes eléctricas. También se puede usar el problema de flujo máximo para encontrar emparejamientos en grafos bipartitos, con múltiples aplicaciones.

Existen diversos algoritmos para resolver el problema del flujo máximo eficientemente, que tienen diferente complejidad computacional dependiendo de las propiedades del grafo en el que se apliquen. Se estudiarán sus diferencias y su implementación eficiente, así como posibles mejoras

[EN]