Goldberg & Tarjan: Como encontrar um fluxo de bloqueio em um gráfico

8

Eu quero implementar o algoritmo Goldberg & Rao para encontrar um fluxo máximo em um gráfico. Meu problema é a etapa de atualização, na qual todos os documentos e relatórios afirmam "No gráfico resultante, encontre um fluxo de bloqueio ou um fluxo de valor Delta". Todos eles se referem à Goldberg & Tarjan para encontrar um fluxo de bloqueio. Há duas coisas que não entendo:

  1. Como devo encontrar um fluxo de valor Delta?
  2. Mas mais importante: como posso encontrar um fluxo de bloqueio?

Com relação às perguntas 2: li os dois artigos (o de Goldberg & Tarjan "Uma nova abordagem para o problema do fluxo máximo" e o de árvores dinâmicas - ambos não eram tão difíceis de entender). Todo artigo / relatório / livro sobre Goldberg & Rao se refere ao artigo de Goldberg & Tarjan e destaca que Goldberg & Rao não usa o algoritmo push / relabel, mas encontra fluxos de bloqueio. Mas, na minha opinião, Tarjan apenas explica o algoritmo push / re-label, não consigo encontrar nada sobre o bloqueio de fluxos.

T. Cormen, "Introdução aos algoritmos", 3ª edição

O algoritmo assintoticamente mais rápido até hoje para o problema de fluxo máximo, por Goldberg e Rao, é executado no tempo , onde . Esse algoritmo não usa o método push-re-label, mas baseia-se na localização de fluxos de bloqueio.O(mEun(V2/3,E1/2)Elg(V2/E+2)lgC)C=maxc(você,v)

A. Goldberg e S. Rao, "Além da barreira de decomposição do fluxo" (o artigo original)

Usando o algoritmo de fluxo de bloqueio de Goldberg e Tarjan [1988], obtemos um limite O(Λmeuog(n2/m)registrovocê) .

user1904159
fonte

Respostas: