No gráfico direcionado, como encontrar muitos pequenos cortes?

7

A solução do problema de vazão máxima gera um corte mínimo qualificado. Mas quero vários (talvez centenas) pequenos cortes como candidatos. Os cortes não precisam ser mínimos, desde que sejam pequenos (em peso). Como faço isso?

algorithms graphs graph-theory optimization approximation steph
fonte
O que é pequeno em peso? Quantos cortes você deseja, um número constante, , ? nn2
Utdiscant
11
Para simplificar, todas as arestas têm um peso de 1 e pequeno significa "o número de arestas de um corte é pequeno, digamos menos de 10, por exemplo". Eu quero cerca de n cortes, por exemplo. ou apenas várias centenas, o que facilita o design. obrigado.
steph 24/05
@steph: Observe que, para pesos unitários, o problema provavelmente cai para um conceitualmente mais simples, portanto, uma solução pode não ajudá-lo no caso geral.
Raphael

Respostas:

3

Você conhece o algoritmo de contração aleatória, também conhecido como algoritmo de Karger ? O algoritmo basicamente funciona selecionando arestas uniformemente aleatoriamente e contratando-as com os auto-loops removidos. O processo é interrompido quando há dois nós restantes e os dois nós representam um corte. Para aumentar a probabilidade de sucesso, o algoritmo aleatório é executado várias vezes. Enquanto faz as corridas, mantém o controle do menor corte encontrado até agora.

O que sugiro agora é que você execute o algoritmo de contração aleatória várias vezes. Sempre que o algoritmo emitir um corte, decida se deve ou não mantê-lo, verificando se é pequeno o suficiente. Naturalmente, você pode parar quando produziu o suficiente desses pequenos cortes. Dependendo do tamanho da sua entrada, isso pode até funcionar muito bem na prática.

Juho
fonte
Ao fazer uma pesquisa profunda em vez da randomização, isso também pode ser usado para obter todos os cortes mínimos ou, alternativamente, aumentar as chances de encontrar novos cortes em cada iteração.
Raphael