A maneira mais rápida de encontrar um st min-cut a partir de um st max-flow?

8

A Ford-Fulkerson pode encontrar fluxos esparsos no tempo linear no tamanho do fluxo e no número de nós se as bordas tiverem capacidade unitária.

Como eu poderia usar um fluxo st esparso para encontrar um st min-cut no tempo proporcional ao tamanho do fluxo e ao número de meus nós, para o caso de fluxo máximo esparso / baixo volume?

graph-algorithms max-flow max-flow-min-cut Elliot JJ
fonte
Existe uma referência rápida para a definição de um fluxo st esparso?
precisa
1. Atravessar todas as arestas e encontrar arestas saturadas parecia bastante legítimo intuitivamente. Mas uma falha é que nem todas as bordas saturadas necessariamente pertencem a um corte minúsculo. 2. Corte mínimo deve ser um conjunto de arestas, não um conjunto de vértices. 3. Portanto, a solução típica deve ser apenas a resposta aceita acima. Na rede de fluxo máximo (dada ou você pode calcular por Ford-Fulkerson ou Edmunds-Karp), DFS ou BFS de s, marque todos os vértices que são alcançáveis ​​(o processo de tentar encontrar um caminho de aumento, mas você sabe
Jinggang

Respostas:

8

tsst

stst

Magnus Lie Hetland
fonte
-1

Existe uma referência rápida para a definição de um fluxo st esparso?

No caso geral, com o fluxo máximo é muito fácil determinar o corte mínimo, via teorema de corte mínimo e fluxo mínimo. As arestas totalmente saturadas formam um conjunto de corte; portanto, ao selecionar um vértice para cada aresta, é possível formar um corte min. Trivialmente, esse é O (m) na pior das hipóteses, e também se alguém torna o tempo de execução sensível à saída, o número de arestas no fluxo ou, melhor ainda, o número de arestas saturadas no fluxo, sempre é superior limite no tempo de execução do algoritmo para encontrar o min-cut do fluxo máximo. Portanto, se você tiver uma modificação que encontre esses fluxos esparsos em tempo linear no tamanho do fluxo, encontrar o min-cut não alterará o tempo de execução do algoritmo assintoticamente.

chazisop
fonte
2
Eu não tenho uma definição específica. Apenas algo em que o ford-fulkerson é assintoticamente mais rápido do que qualquer outra coisa. Se todas as minhas arestas tiverem capacidade unitária, muitas delas não serão saturadas, incluindo arestas que, se removidas, poderiam ser facilmente substituídas sem afetar o volume máximo de fluxo? Eu poderia remover todas essas arestas e formar um corte, mas não tenho certeza de como substituiria as que não precisei remover.
precisa saber é o seguinte
Depende do gráfico. Se você tivesse capacidades unitárias e um gráfico denso, é bem provável que você tivesse muitos fluxos com valor máximo; isso, por sua vez, poderia ser interpretado como se você tivesse um grande número de min-cortes diferentes. Dê uma olhada também em esta referência: en.wikipedia.org/wiki/Max-flow_min-cut_theorem
chazisop