graph - teorema - Todos los pares flujo máximo

flujo maximo youtube

Question

Dado un gráfico ponderado dirigido, cómo encontrar el flujo máximo (o el corte mínimo del borde ) entre todos los pares de vértices.
El enfoque ingenuo es simplemente llamar a un algoritmo de flujo máximo como el de Dinic, cuya complejidad es O((V^2)*E) para cada par.
Por lo tanto, para todos los pares es O((V^4)*E) .

¿Es posible reducir la complejidad a O((V^3)*E) oa O(V^3) mediante algunas optimizaciones?

Answer 1

El árbol de Gomory-Hu no funciona para gráficos ponderados dirigidos.

Es un problema abierto si existe un algoritmo para resolver todo el flujo máximo de par más rápido que ejecutar n ^ 2 flujos máximos en gráficos dirigidos.

Answer 2

Gomory-Hu Tree no trabaja con gráficos dirigidos , dejando eso de lado, Gomory-Hu Tree formará un flujo máximo de Gráfico aplicando cortes mínimos.

La complejidad del tiempo es:

O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)

* utilizando un algoritmo de corte mínimo óptimo ( Reducción mínima de corte de flujo máximo )

Este ejemplo ilustra cómo se construye Gomory-Hu Tree a partir de un gráfico dado