En la teoría de la optimización , los problemas de caudal máximo implican encontrar un caudal factible a través de una red de caudal que obtenga el caudal máximo posible.
El problema de flujo máximo puede verse como un caso especial de problemas de flujo de red más complejos, como el problema de circulación . El valor máximo de un flujo st (es decir, el flujo desde la fuente s al sumidero t) es igual a la capacidad mínima de un corte st (es decir, el corte seccionando s de t) en la red, como se indica en el flujo máximo mín. teorema de corte .
Historia
El problema de flujo máximo fue formulado por primera vez en 1954 por TE Harris y FS Ross como un modelo simplificado del flujo de tráfico ferroviario soviético. [1] [2] [3]
En 1955, Lester R. Ford, Jr. y Delbert R. Fulkerson crearon el primer algoritmo conocido, el algoritmo Ford-Fulkerson . [4] [5] En su artículo de 1955, [4] Ford y Fulkerson escribieron que el problema de Harris y Ross se formula de la siguiente manera (ver [1] p. 5):
Considere una red ferroviaria que conecta dos ciudades a través de varias ciudades intermedias, donde cada enlace de la red tiene asignado un número que representa su capacidad. Suponiendo una condición de estado estable, encuentre un flujo máximo de una ciudad determinada a la otra.
En su libro Flows in Network , [5] en 1962, Ford y Fulkerson escribieron:
Fue planteado a los autores en la primavera de 1955 por TE Harris, quien, junto con el general FS Ross (Ret.), Había formulado un modelo simplificado de flujo de tráfico ferroviario, y señaló este problema particular como el central sugerido por el modelo [11].
donde [11] se refiere al informe secreto de 1955 Fundamentos de un método para evaluar las capacidades de las redes ferroviarias de Harris y Ross [3] (ver [1] p. 5).
A lo largo de los años, se descubrieron varias soluciones mejoradas para el problema de flujo máximo, en particular el algoritmo de ruta de aumento más corto de Edmonds y Karp e independientemente Dinitz; el algoritmo de bloqueo de flujo de Dinitz; el algoritmo push-reetiquetado de Goldberg y Tarjan ; y el algoritmo de flujo de bloqueo binario de Goldberg y Rao. Los algoritmos de Sherman [6] y Kelner, Lee, Orecchia y Sidford, [7] [8] respectivamente, encuentran un flujo máximo aproximadamente óptimo pero solo funcionan en gráficos no dirigidos.
En 2013, James B. Orlin publicó un artículo que describía unaalgoritmo. [9]
Definición
Primero establecemos alguna notación:
- Dejar ser una red con siendo la fuente y el sumidero de respectivamente.
- Si es función en los bordes de entonces su valor en se denota por o
Definición. La capacidad de un borde es la cantidad máxima de flujo que puede pasar a través de un borde. Formalmente es un mapa
Definición. Un flujo es un mapa que satisfaga lo siguiente:
- Limitación de capacidad . El flujo de un borde no puede exceder su capacidad, es decir: para todos
- Conservación de caudales. La suma de los flujos que ingresan a un nodo debe ser igual a la suma de los flujos que salen de ese nodo, excepto la fuente y el sumidero. O:
Observación . Los flujos son simétricos sesgados: para todos
Definición. El valor del flujo es la cantidad de flujo que pasa de la fuente al sumidero. Formalmente para un flujo está dado por:
Definición. El problema de flujo máximo es enrutar tanto flujo como sea posible desde la fuente hasta el sumidero, en otras palabras, encontrar el flujo con valor máximo.
Tenga en cuenta que pueden existir varios flujos máximos, y si se permiten valores de flujo arbitrarios reales (o incluso racionales arbitrarios) (en lugar de solo números enteros), hay exactamente un flujo máximo o infinitos, ya que hay infinitas combinaciones lineales de los flujos máximos base. En otras palabras, si enviamos unidades de flujo en el borde en un flujo máximo, y unidades de flujo en en otro flujo máximo, luego para cada podemos enviar unidades en y enrute el flujo en los bordes restantes en consecuencia, para obtener otro flujo máximo. Si los valores de flujo pueden ser números reales o racionales, entonces hay infinitos valores para cada par .
Algoritmos
La siguiente tabla enumera los algoritmos para resolver el problema de flujo máximo.
Método | Complejidad | Descripción |
---|---|---|
Programación lineal | Restricciones dadas por la definición de flujo legal . Vea el programa lineal aquí. | |
Algoritmo de Ford-Fulkerson | Siempre que haya un camino abierto a través del gráfico residual, envíe el mínimo de las capacidades residuales en el camino. Solo se garantiza que el algoritmo terminará si todos los pesos son racionales , en cuyo caso la cantidad agregada al flujo en cada paso es al menos el máximo común divisor de los pesos. De lo contrario, es posible que el algoritmo no converja al valor máximo. Sin embargo, si el algoritmo termina, se garantiza que encontrará el valor máximo. | |
Algoritmo de Edmonds-Karp | Una especialización de Ford-Fulkerson, que encuentra caminos cada vez mayores con una búsqueda que prioriza la amplitud . | |
Algoritmo de Dinic | En cada fase, los algoritmos construyen un gráfico en capas con búsqueda de amplitud primero en el gráfico residual . El flujo máximo en un gráfico en capas se puede calcular en tiempo, y el número máximo de fases es . En redes con capacidades unitarias, el algoritmo de Dinic termina enhora. [ cita requerida ] | |
Algoritmo MKM (Malhotra, Kumar, Maheshwari) [10] | Una modificación del algoritmo de Dinic con un enfoque diferente para construir flujos de bloqueo. Consulte el papel original . | |
Algoritmo de Dinic con árboles dinámicos | La estructura de datos de árboles dinámicos acelera el cálculo de flujo máximo en el gráfico en capas para. | |
Algoritmo general de inserción y reetiquetado [11] | El algoritmo push relabel mantiene un preflujo, es decir, una función de flujo con posibilidad de exceso en los vértices. El algoritmo se ejecuta mientras hay un vértice con exceso positivo, es decir, un vértice activo en el gráfico. La operación de empuje aumenta el flujo en un borde residual, y una función de altura en los vértices controla a través de los cuales se pueden empujar los bordes residuales. La función de altura se cambia mediante la operación de reetiquetado. Las definiciones adecuadas de estas operaciones garantizan que la función de flujo resultante sea un flujo máximo. | |
Algoritmo push-reetiquetado con regla de selección de vértice FIFO [11] | Variante del algoritmo push-reetiquetado que siempre selecciona el vértice activo más recientemente y realiza operaciones push mientras el exceso es positivo y hay bordes residuales admisibles de este vértice. | |
Algoritmo push-reetiquetado con regla de selección de vértice de distancia máxima [12] | Variante de algoritmo push-reetiquetado que siempre selecciona el vértice más distante de o (es decir, el vértice de la etiqueta más alta) pero por lo demás procede como el algoritmo FIFO. | |
Algoritmo push-reetiquetado con árboles dinámicos [11] | El algoritmo construye árboles de tamaño limitado en el gráfico residual con respecto a la función de altura. Estos árboles proporcionan operaciones de empuje de varios niveles, es decir, empujando a lo largo de una ruta de saturación completa en lugar de un solo borde. | |
Algoritmo de KRT (King, Rao, Tarjan) [13] | ||
Algoritmo de flujo de bloqueo binario [14] | El valor U corresponde a la capacidad máxima de la red. | |
Algoritmo de James B Orlin + KRT (King, Rao, Tarjan) [9] | El algoritmo de Orlin resuelve el flujo máximo en tiempo para mientras que KRT lo resuelve en por . | |
Algoritmo de Kathuria-Liu-Sidford [15] | Métodos de puntos interiores y refuerzo de bordes usando -flujos normales. Se basa en el algoritmo anterior de Madry, que logró el tiempo de ejecución.. [dieciséis] | |
Algoritmo BLNPSSSW / BLLSSSW [17] [18] | Métodos de puntos interiores y mantenimiento dinámico de flujos eléctricos con descomposición de expansores. | |
Algoritmo de Gao-Liu-Peng [19] | El algoritmo de Gao, Liu y Peng gira en torno al mantenimiento dinámico de los flujos eléctricos crecientes en el núcleo del algoritmo basado en el método del punto interior de [Mądry JACM '16]. Esto implica diseñar estructuras de datos que, en entornos limitados, devuelvan bordes con gran energía eléctrica en un gráfico que experimenta actualizaciones de resistencia. |
Para obtener una lista más extensa, consulte Goldberg y Tarjan (1988) .
Teorema del flujo integral
El teorema del flujo integral establece que
- Si cada borde en una red de flujo tiene capacidad integral, entonces existe un flujo máximo integral.
Solicitud
Problema de flujo máximo de múltiples fuentes y múltiples sumideros
Dada una red con un conjunto de fuentes y un juego de lavabos en lugar de solo una fuente y un sumidero, debemos encontrar el flujo máximo a través . Podemos transformar el problema de múltiples fuentes de múltiples sumideros en un problema de flujo máximo agregando una fuente consolidada que se conecte a cada vértice eny un sumidero consolidado conectado por cada vértice en(también conocido como SuperSource y supersink ) con capacidad infinita en cada borde (véase la Fig. 4.1.1.).
Coincidencia bipartita de cardinalidad máxima
Dado un gráfico bipartito , debemos encontrar una coincidencia máxima de cardinalidad en, es una coincidencia que contiene el mayor número posible de aristas. Este problema se puede transformar en un problema de flujo máximo mediante la construcción de una red., dónde
- contiene los bordes en dirigido desde a .
- para cada y para cada .
- para cada (Ver Fig. 4.3.1).
Entonces el valor del caudal máximo en es igual al tamaño de la coincidencia máxima en .
Cobertura de trayectoria mínima en gráfico acíclico dirigido
Dado un gráfico acíclico dirigido , debemos encontrar el número mínimo de caminos disjuntos de vértice para cubrir cada vértice en. Podemos construir un grafo bipartito de , dónde
- .
Entonces se puede demostrar que tiene una coincidencia de tamaño si y solo si tiene una cubierta de ruta disjunta de vértice de contener bordes y caminos, donde es el número de vértices en . Por lo tanto, el problema puede resolverse encontrando la máxima coincidencia de cardinalidad en en lugar de.
Intuitivamente, si dos vértices están emparejados en , luego el borde está contenido en . Claramente el número de aristas en es . Para ver eso es vértice-disjunto, considere lo siguiente:
- Cada vértice en puede no coincidir en, en cuyo caso no quedan bordes en ; o se puede combinar , en cuyo caso hay exactamente un borde dejando en . En cualquier caso, no más de una arista sale de ningún vértice en .
- De manera similar para cada vértice en - si coincide, hay un solo borde entrante en en ; de lo contrario no tiene bordes entrantes en .
Por tanto, ningún vértice tiene dos aristas entrantes o dos salientes en , lo que significa todos los caminos en son vértice-disjuntos.
Para mostrar que la portada tiene tamaño , comenzamos con una cubierta vacía y la construimos de forma incremental. Para agregar un vérticea la portada, podemos agregarlo a una ruta existente o crear una nueva ruta de longitud cero comenzando en ese vértice. El primer caso es aplicable siempre que y algún camino en la portada comienza en , o y algún camino termina en . El último caso es siempre aplicable. En el primer caso, el número total de bordes en la cubierta se incrementa en 1 y el número de caminos permanece igual; en el último caso, el número de trayectorias aumenta y el número de aristas permanece igual. Ahora está claro que después de cubrir todo vértices, la suma del número de caminos y aristas en la portada es . Por lo tanto, si el número de bordes de la cubierta es, el número de caminos es .
Caudal máximo con capacidades de vértice
Dejar ser una red. Suponga que hay capacidad en cada nodo además de la capacidad de borde, es decir, un mapeo tal que el flujo tiene que satisfacer no solo la restricción de capacidad y la conservación de los flujos, sino también la restricción de capacidad del vértice
En otras palabras, la cantidad de flujo que pasa por un vértice no puede exceder su capacidad. Para encontrar el flujo máximo a través, podemos transformar el problema en el problema de flujo máximo en el sentido original expandiendo . Primero, cada es reemplazado por y , dónde está conectado por bordes que entran y está conectado a los bordes que salen de , luego asigne capacidad hasta el borde conectando y (ver Fig. 4.4.1). En esta red expandida, la restricción de capacidad de vértice se elimina y, por lo tanto, el problema puede tratarse como el problema de flujo máximo original.
Número máximo de trayectos de sa t
Dado un gráfico dirigido y dos vértices y , debemos encontrar el número máximo de rutas desde a . Este problema tiene varias variantes:
1. Los caminos deben estar separados de los bordes. Este problema se puede transformar en un problema de flujo máximo mediante la construcción de una red. de , con y siendo la fuente y el sumidero de respectivamente, y asignando a cada borde una capacidad de . En esta red, el caudal máximo es si hay caminos de borde disjuntos.
2. Los caminos deben ser independientes, es decir, disjuntos de vértice (excepto para y ). Podemos construir una red de con capacidades de vértice, donde las capacidades de todos los vértices y todos los bordes son . Entonces el valor del flujo máximo es igual al número máximo de caminos independientes de a .
3. Además de que las rutas son disjuntos de borde y / o vértice, las rutas también tienen una restricción de longitud: solo contamos las rutas cuya longitud es exactamente , o como mucho . La mayoría de las variantes de este problema son NP-completas, excepto por pequeños valores de. [20]
Problema de cierre
Un cierre de un grafo dirigido es un conjunto de vértices C , de manera que no hay bordes dejan C . El problema de cierre es la tarea de encontrar el cierre de peso máximo o de peso mínimo en un gráfico dirigido ponderado por vértice. Puede resolverse en tiempo polinomial utilizando una reducción al problema de flujo máximo.
Aplicaciones del mundo real
Eliminación de béisbol
En el problema de la eliminación del béisbol , hay n equipos compitiendo en una liga. En una etapa específica de la temporada de la liga, w i es el número de victorias y r i es el número de juegos que quedan por jugar para el equipo i y r ij es el número de juegos que quedan contra el equipo j . Un equipo es eliminado si no tiene la oportunidad de terminar la temporada en primer lugar. La tarea del problema de eliminación del béisbol es determinar qué equipos son eliminados en cada punto durante la temporada. Schwartz [21] propuso un método que reduce este problema al máximo flujo de red. En este método se crea una red para determinar si se elimina el equipo k .
Sea G = ( V , E ) una red con s , siendo t ∈ V la fuente y el sumidero respectivamente. Uno agrega un nodo de juego { i , j } con i < j a V , y conecta cada uno de ellos desde s por un borde con capacidad r ij , que representa el número de jugadas entre estos dos equipos. También agregamos un nodo de equipo para cada equipo y conectamos cada nodo de juego { i , j } con dos nodos de equipo i y j para asegurarnos de que uno de ellos gane. No es necesario restringir el valor de flujo en estos bordes. Finalmente, los bordes se hacen desde el nodo del equipo i al nodo sumidero t y la capacidad de w k + r k - w i se establece para evitar que el equipo i gane más de w k + r k . Sea S el conjunto de todos los equipos que participan en la liga y sea. En este método se afirma equipo k no se elimina si y sólo si un valor de flujo de tamaño r ( S - { k }) existe en la red G . En el artículo mencionado se demuestra que este valor de flujo es el valor del flujo máximo de s a t .
Programación de aerolíneas
En la industria de las aerolíneas, un problema importante es la programación de las tripulaciones de vuelo. El problema de la programación de la aerolínea puede considerarse como una aplicación del flujo máximo extendido de la red. La entrada de este problema es un conjunto de vuelos F que contiene la información sobre dónde y cuándo sale y llega cada vuelo. En una versión de la programación de las aerolíneas, el objetivo es producir un programa factible con un máximo de k tripulaciones.
Para resolver este problema, se utiliza una variación del problema de circulación llamado circulación limitada, que es la generalización de los problemas de flujo de la red , con la restricción adicional de un límite inferior en los flujos de borde.
Sea G = ( V , E ) una red con s , t ∈ V como los nodos fuente y sumidero. Para la fuente y el destino de cada vuelo i , se agregan dos nodos a V , el nodo s i como la fuente y el nodo d i como el nodo de destino del vuelo i . También se agregan los siguientes bordes a E :
- Una arista con capacidad [0, 1] entre sy cada s i .
- Una arista con capacidad [0, 1] entre cada d i y t .
- Una arista con capacidad [1, 1] entre cada par de s i y d i .
- Un borde con capacidad [0, 1] entre cada d i y s j , si la fuente s j es alcanzable con una cantidad razonable de tiempo y costo desde el destino del vuelo i .
- Un borde con capacidad de [0, ∞ ] entre s y t .
En el método mencionado, se afirma y demostró que la búsqueda de un valor de flujo de k en G entre s y t es igual a la búsqueda de un horario factible para el vuelo establecido F con al mayoría de k tripulaciones. [22]
Otra versión de la programación de las aerolíneas es encontrar las tripulaciones mínimas necesarias para realizar todos los vuelos. Con el fin de encontrar una respuesta a este problema, un grafo bipartito G' = ( A ∪ B , E ) se crea en cada vuelo tiene una copia en el conjunto A y el conjunto B . Si el mismo plano puede realizar vuelo j después de vuelo i , i ∈ A está conectado a j ∈ B . Una coincidencia en G ' induce un horario para F y, obviamente, la máxima coincidencia bipartita en este gráfico produce un horario de línea aérea con un número mínimo de tripulaciones. [22] Como se menciona en la parte Aplicación de este artículo, la coincidencia bipartita de cardinalidad máxima es una aplicación del problema de flujo máximo.
Problema de circulación-demanda
Hay algunas fábricas que producen bienes y algunos pueblos donde los bienes deben entregarse. Están conectados por una red de carreteras y cada carretera tiene una capacidad c para el máximo de mercancías que pueden fluir a través de ella. El problema es encontrar si existe una circulación que satisfaga la demanda. Este problema puede transformarse en un problema de flujo máximo.
- Agregue un nodo de origen sy agregue bordes desde él a cada nodo de fábrica f i con capacidad p i donde p i es la tasa de producción de la fábrica f i .
- Añadir un nodo receptor, t y añadir bordes de todos los pueblos v i a camiseta T con capacidad d i , donde D i es la tasa de demanda del pueblo v i .
Sea G = ( V , E ) esta nueva red. Existe una circulación que satisface la demanda si y solo si:
- Valor de flujo máximo ( G ).
Si existe una circulación, mirar la solución de flujo máximo daría la respuesta sobre la cantidad de mercancías que deben enviarse por una carretera en particular para satisfacer las demandas.
El problema se puede ampliar agregando un límite inferior al flujo en algunos bordes. [23]
Segmentación de imagen
En su libro, Kleinberg y Tardos presentan un algoritmo para segmentar una imagen. [25] Presentan un algoritmo para encontrar el fondo y el primer plano en una imagen. Más precisamente, el algoritmo toma un mapa de bits como entrada modelada de la siguiente manera: a i ≥ 0 es la probabilidad de que el píxel i pertenezca al primer plano, b i ≥ 0 en la probabilidad de que el píxel i pertenezca al fondo y p ij es penalización si dos píxeles adyacentes i y j se colocan uno en primer plano y el otro en el fondo. El objetivo es encontrar una partición ( A , B ) del conjunto de píxeles que maximice la siguiente cantidad
- ,
De hecho, para los píxeles en A (considerados como el primer plano), obtenemos una i ; para todos los píxeles de B (considerados como el fondo), obtenemos b i . En el borde, entre dos píxeles adyacentes i y j , perdemos p ij . Equivale a minimizar la cantidad
porque
Ahora construimos la red cuyos nodos son el píxel, más una fuente y un sumidero, vea la Figura a la derecha. Conectamos la fuente al píxel i por un borde de peso a i . Conectamos el píxel i al fregadero por un borde de peso b i . Conectamos el píxel i al píxel j con peso p ij . Ahora, queda por calcular un corte mínimo en esa red (o equivalentemente un flujo máximo). La última figura muestra un corte mínimo.
Extensiones
1. En el problema de flujo de costo mínimo , cada borde ( u , v) también tiene un coeficiente de costo a uv además de su capacidad. Si el flujo a través del borde es f uv , entonces el costo total es un uv f uv . Se requiere encontrar un flujo de un tamaño d dado , con el menor costo. En la mayoría de las variantes, los coeficientes de costo pueden ser positivos o negativos. Existen varios algoritmos de tiempo polinomial para este problema.
2. El problema de flujo máximo puede aumentarse mediante restricciones disyuntivas : una restricción disyuntiva negativa dice que un cierto par de aristas no puede tener simultáneamente un flujo distinto de cero; una restricción disyuntiva positiva dice que, en un cierto par de aristas, al menos uno debe tener un flujo distinto de cero. Con restricciones negativas, el problema se vuelve fuertemente NP-difícil incluso para redes simples. Con restricciones positivas, el problema es polinómico si se permiten flujos fraccionarios, pero puede ser fuertemente NP-duro cuando los flujos deben ser integrales. [26]
Referencias
- ↑ a b c Schrijver, A. (2002). "Sobre la historia de los problemas de transporte y caudal máximo". Programación matemática . 91 (3): 437–445. CiteSeerX 10.1.1.23.5134 . doi : 10.1007 / s101070100259 . S2CID 10210675 .
- ^ Gass, Saul I .; Assad, Arjang A. (2005). "Desarrollos matemáticos, algorítmicos y profesionales de la investigación de operaciones desde 1951 hasta 1956". Una cronología comentada de la investigación operativa . Serie Internacional en Investigación de Operaciones y Ciencias de la Gestión. 75 . págs. 79–110. doi : 10.1007 / 0-387-25837-X_5 . ISBN 978-1-4020-8116-3.
- ^ a b Harris, TE ; Ross, FS (1955). "Fundamentos de un método para evaluar las capacidades de la red ferroviaria" (PDF) . Memorando de investigación .
- ^ a b Ford, LR ; Fulkerson, DR (1956). "Flujo máximo a través de una red". Revista canadiense de matemáticas . 8 : 399–404. doi : 10.4153 / CJM-1956-045-5 .
- ^ a b Ford, LR, Jr .; Fulkerson, RD, Flujos en redes , Princeton University Press (1962).
- ^ Sherman, Jonah (2013). "Caudales casi máximos en tiempo casi lineal". Actas del 54º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación . págs. 263–269. arXiv : 1304.2077 . doi : 10.1109 / FOCS.2013.36 . ISBN 978-0-7695-5135-7. S2CID 14681906 .
- ^ Kelner, JA; Lee, YT; Orecchia, L .; Sidford, A. (2014). "Un algoritmo de tiempo casi lineal para el flujo máximo aproximado en gráficos no dirigidos y sus generalizaciones de múltiples productos" (PDF) . Actas del Vigésimo Quinto Simposio Anual ACM-SIAM sobre Algoritmos Discretos . pag. 217. arXiv : 1304.2338 . doi : 10.1137 / 1.9781611973402.16 . ISBN 978-1-61197-338-9. S2CID 10733914 . Archivado desde el original (PDF) el 3 de marzo de 2016.
- ^ Knight, Helen (7 de enero de 2014). "El nuevo algoritmo puede agilizar drásticamente las soluciones al problema del 'flujo máximo'" . Noticias del MIT . Consultado el 8 de enero de 2014 .
- ^ a b Orlin, James B. (2013). "Flujos máximos en tiempo O (nm), o mejor". Actas del 45º simposio anual de ACM sobre el Simposio sobre teoría de la computación - STOC '13 . STOC '13 Actas del cuadragésimo quinto simposio anual ACM sobre teoría de la computación . págs. 765–774. CiteSeerX 10.1.1.259.5759 . doi : 10.1145 / 2488608.2488705 . ISBN 9781450320290. S2CID 207205207 .
- ^ Malhotra, VM; Kumar, M. Pramodh; Maheshwari, SN (1978). "Un O ( | V | 3 ) {\ Displaystyle O (| V | ^ {3})} algoritmo para encontrar flujos máximos en redes " (PDF) . Information Processing Letters . 7 (6): 277–278. doi : 10.1016 / 0020-0190 (78) 90016-9 .
- ^ a b c Goldberg, AV ; Tarjan, RE (1988). "Un nuevo enfoque al problema del caudal máximo" . Revista de la ACM . 35 (4): 921. doi : 10.1145 / 48014.61051 . S2CID 52152408 .
- ^ Cheriyan, J .; Maheshwari, SN (1988). "Análisis de algoritmos push de preflujo para máximo flujo de red". Fundamentos de la tecnología del software y la informática teórica . Apuntes de conferencias en Ciencias de la Computación. 338 . págs. 30–48. doi : 10.1007 / 3-540-50517-2_69 . ISBN 978-3-540-50517-4. ISSN 0302-9743 .
- ^ King, V .; Rao, S .; Tarjan, R. (1994). "Un algoritmo de flujo máximo determinista más rápido". Revista de algoritmos . 17 (3): 447–474. doi : 10.1006 / jagm.1994.1044 . S2CID 15493 .
- ^ Goldberg, AV ; Rao, S. (1998). "Más allá de la barrera de descomposición del flujo". Revista de la ACM . 45 (5): 783. doi : 10.1145 / 290179.290181 . S2CID 96030 .
- ^ Kathuria, T .; Liu, YP; Sidford, A. (16 al 19 de noviembre de 2020). Capacidad de la unidad Maxflow en casiTiempo . Durham, NC, Estados Unidos: IEEE. págs. 119–130.Mantenimiento CS1: formato de fecha ( enlace )
- ^ Madry, Aleksander (9 a 11 de octubre de 2016). Calcular el flujo máximo con el aumento de los flujos eléctricos . Nuevo Brunswick, Nueva Jersey: IEEE. págs. 593–602.Mantenimiento CS1: formato de fecha ( enlace )
- ^ Brand, J. vd; Lee, YT; Nanongkai, D .; Peng, R .; Saranurak, T .; Sidford, A .; Song, Z .; Wang, D. (16 al 19 de noviembre de 2020). Coincidencia bipartita en un tiempo casi lineal en gráficos moderadamente densos . Durham, NC, Estados Unidos: IEEE. págs. 919–930.Mantenimiento CS1: formato de fecha ( enlace )
- ^ Brand, J. vd; Lee, YT; Liu, YP; Saranurak, T .; Sidford, A; Song, Z .; Wang, D. (2021). "Flujos de costo mínimo, MDP y regresión ℓ1 en tiempo casi lineal para instancias densas". arXiv : 2101.05719 [ cs.DS ].
- ^ Gao, Y .; Liu, YP; Peng, R. (2021). "Flujos eléctricos totalmente dinámicos: Maxflow disperso más rápido que Goldberg-Rao". arXiv : 2101.07233 [ cs.DS ].
- ^ Itai, A .; Perl, Y .; Shiloach, Y. (1982). "La complejidad de encontrar caminos disjuntos máximos con restricciones de longitud". Redes . 12 (3): 277–286. doi : 10.1002 / net.3230120306 . ISSN 1097-0037 .
- ^ Schwartz, BL (1966). "Posibles ganadores en torneos parcialmente completados". Revisión SIAM . 8 (3): 302–308. Código Bibliográfico : 1966SIAMR ... 8..302S . doi : 10.1137 / 1008062 . JSTOR 2028206 .
- ^ a b Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001). "26. Caudal máximo". Introducción a los algoritmos, segunda edición . MIT Press y McGraw-Hill. págs. 643–668. ISBN 978-0-262-03293-3.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Carl Kingsford. "Extensiones de caudal máximo: circulaciones con demandas" (PDF) .
- ^ "Project imagesegmentationwithmaxflow, que contiene el código fuente para producir estas ilustraciones" . GitLab . Archivado desde el original el 22 de diciembre de 2019 . Consultado el 22 de diciembre de 2019 .
- ^ "Diseño de algoritmos" . www.pearson.com . Consultado el 21 de diciembre de 2019 .
- ^ Schauer, Joachim; Pferschy, Ulrich (1 de julio de 2013). "El problema de flujo máximo con restricciones disyuntivas". Revista de optimización combinatoria . 26 (1): 109-119. CiteSeerX 10.1.1.414.4496 . doi : 10.1007 / s10878-011-9438-7 . ISSN 1382-6905 . S2CID 6598669 .
Otras lecturas
- Joseph Cheriyan y Kurt Mehlhorn (1999). "Un análisis de la regla de selección de más alto nivel en el algoritmo de flujo máximo de empuje de preflujo". Cartas de procesamiento de información . 69 (5): 239–242. CiteSeerX 10.1.1.42.8563 . doi : 10.1016 / S0020-0190 (99) 00019-8 .
- Daniel D. Sleator y Robert E. Tarjan (1983). "Una estructura de datos para árboles dinámicos" (PDF) . Revista de Ciencias de la Computación y Sistemas . 26 (3): 362–391. doi : 10.1016 / 0022-0000 (83) 90006-5 . ISSN 0022-0000 .
- Eugene Lawler (2001). "4. Flujos de red". Optimización combinatoria: redes y matroides . Dover. págs. 109-177. ISBN 978-0-486-41453-9.