Esta pregunta es sobre la complejidad temporal del algoritmo de flujo máximo de Ford-Fulkerson cuando se usa DFS para encontrar rutas de aumento.
Hay un ejemplo bien conocido que muestra que el uso de DFS puede necesitar un número lineal de iteraciones en el flujo máximo; consulte, por ejemplo, la página de Wikipedia vinculada anteriormente.
Sin embargo, no estoy realmente convencido con este ejemplo: una implementación estándar de DFS no exhibiría el comportamiento de alternar entre B y C como primer nodo de la ruta (usando los nombres de vértices de la página de Wikipedia).
Entonces, impongamos la condición muy natural de que cada vez que el DFS visita un nodo , siempre examina a los vecinos de u en el mismo orden. ¿Todavía hay ejemplos para los que FF con DFS usa una gran cantidad de iteraciones?
Como variante, suponga que tenemos la propiedad adicional de que los diferentes ordenamientos de vecinos son consistentes con algún ordenamiento global arbitrario pero fijo de los vértices. Eso hace una diferencia?
Esto me parece una pregunta bastante básica; Pido disculpas de antemano si la respuesta es conocida, pero no soy un experto en flujos y algunas búsquedas en Google no arrojaron nada.
Editar: La respuesta resulta ser sí, todavía hay ejemplos. Ver Figura 2 de este documento . En estos ejemplos, FF con DFS toma un número exponencial (en el número de vértices) de iteraciones. Parece fácil demostrar que esto es estricto, es decir, que el número de iteraciones siempre está limitado por (independientemente de los valores de las capacidades).
fuente
Respuestas:
Si las listas de adyacencia se arreglan por adelantado, DFS siempre termina (incluso si hay capacidades irracionales).
Ver Dean, Goemans, Immorlica: terminación finita de los algoritmos de "ruta de aumento" en presencia de datos de problemas irracionales .
fuente