Goldberg y Tarjan: cómo encontrar un flujo de bloqueo en un gráfico

8

Quiero implementar el algoritmo Goldberg & Rao para encontrar un flujo máximo en un gráfico. Mi problema es el paso de actualización donde cada documento e informe indica "En el gráfico resultante, encuentre un flujo de bloqueo o un flujo de valor Delta". Todos se refieren a Goldberg y Tarjan para encontrar un flujo de bloqueo. Hay dos cosas que no entiendo:

  1. ¿Cómo se supone que debo encontrar un flujo de valor Delta?
  2. Pero más importante: ¿cómo puedo encontrar un flujo de bloqueo?

Con respecto a las preguntas 2: leí los dos documentos (el de Goldberg y Tarjan "Un nuevo enfoque para el problema del flujo máximo" y el de los árboles dinámicos, ambos no fueron tan difíciles de entender). Cada artículo / informe / libro sobre Goldberg & Rao se refiere al artículo de Goldberg & Tarjan y destaca que Goldberg & Rao no utiliza el algoritmo push / reetiquetado sino que encuentra flujos de bloqueo. Pero en mi opinión, Tarjan solo explica el algoritmo push / relabel, no puedo encontrar nada sobre el bloqueo de flujos.

T. Cormen, "Introducción a los algoritmos", 3ª edición

El algoritmo asintóticamente más rápido hasta la fecha para el problema de flujo máximo, por Goldberg y Rao, se ejecuta en el tiempo , donde . Este algoritmo no utiliza el método push-relabel, sino que se basa en encontrar flujos de bloqueo.O(min(V2/3,E1/2)Elg(V2/E+2)lgC)C=maxc(u,v)

A. Goldberg y S. Rao, "Más allá de la barrera de descomposición del flujo" (el documento original)

Usando el algoritmo de flujo de bloqueo de Goldberg y Tarjan [1988], obtenemos un límite O(Λmlog(n2/m)logU) .

usuario1904159
fuente

Respuestas: