Ford-Fulkerson puede encontrar flujos dispersos en el tiempo lineales en el tamaño del flujo y el número de nodos si los bordes tienen capacidad unitaria.
¿Cómo podría usar un flujo st disperso para encontrar un corte st min en el tiempo proporcional al tamaño del flujo y el número de mis nodos, para el caso de flujo máximo escaso / bajo volumen?
graph-algorithms
max-flow
max-flow-min-cut
Elliot JJ
fuente
fuente
Respuestas:
Si no usa el flujo per se, pero usa el algoritmo Ford-Fulkerson (o alguna versión, como Edmonds-Karp), puede obtener tanto el flujo máximo como el corte mínimo directamente como resultado. Cuando busca rutas de aumento, realiza un recorrido, en el que usa alguna forma de cola de nodos aún no visitados (en la versión Edmonds-Karp, usa BFS, que significa una cola FIFO). En la última iteración, no puede alcanzar desde (este es el criterio de terminación, después de todo). En este punto, el conjunto de nodos que alcanzó forma la parte del corte, mientras que los nodos que no alcanzó forman la parte .t s s t
Los nodos de la hoja de su árbol transversal forman la "franja" de la parte , mientras que los nodos en su cola transversal forman la franja de la parte , y lo que desea es el conjunto de bordes desde la -fringe a la -fringe. Esto también se puede mantener fácilmente durante el recorrido: simplemente agregue un borde al corte cuando se examina, y conduce a un nodo no visitado, y retírelo si se atraviesa (para que su objetivo sea visitado). Luego, una vez que Ford-Fulkerson haya terminado, tendrás tu corte mínimo (o, mejor dicho, uno de ellos) allí mismo. El tiempo de ejecución será (asintóticamente) idéntico a Ford-Fulkerson (o Edmonds-Karp o cualquier versión que esté usando), lo que debería darle lo que estaba buscando.s t s t
fuente
¿Existe una referencia rápida para la definición de un flujo st disperso?
En el caso general, tener el flujo máximo es bastante fácil de determinar el corte mínimo, a través del teorema de flujo mínimo, corte mínimo. Los bordes que están completamente saturados forman un conjunto de corte, por lo que al seleccionar un vértice para cada borde, se puede formar un corte mínimo. Trivialmente, esto es O (m) en el peor de los casos, y también si uno hace que el tiempo de ejecución sea sensible a la salida, entonces el número de bordes en el flujo o incluso mejor, el número de bordes saturados en el flujo, siempre es superior dependiente del tiempo de ejecución del algoritmo para encontrar el corte mínimo del flujo máximo. Entonces, si tiene una modificación que encuentra esos flujos dispersos en tiempo lineal en el tamaño del flujo, encontrar el corte mínimo no cambiará el tiempo de ejecución del algoritmo asintóticamente.
fuente