Particionamento de gráfico, balanceamento dentro dos pesos das arestas do subconjunto

8

Estou interessado em ponteiros para algoritmos (algoritmos de aproximação são bons) que tentam particionar um gráfico em dois subconjuntos, de modo que a soma dos pesos das arestas em cada subconjunto seja (aproximadamente) igual e a soma dos pesos das arestas entre os dois subconjuntos é (aproximadamente) mínimo.

Qualquer ponteiro é muito apreciado.

PeterR
fonte

Respostas:

9

O problema é chamado de GRAPH CONDUCTANCE, e o melhor algoritmo é de Arora et al.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Fluxos de expansores, incorporação geométrica e particionamento de gráficos. J. ACM 56 (2): (2009)

Esta é uma versão mais acessível , pelos mesmos autores:

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometria, fluxos e algoritmos de particionamento de gráficos. Comum. ACM 51 (10): 96-105 (2008)

Yixin Cao
fonte