O problema do multicorte dirigido mínimo / The directed multicut problem
AUTOR(ES)
Juan Gabriel Gutierrez Alva
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
07/12/2012
RESUMO
O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma análise dos algoritmos exatos e de aproximação para resolver o problema. Também implementa alguns desses algoritmos e compara seus desempenhos.
ASSUNTO(S)
algorithms in graphs algoritmos em grafos directed multicut graph theory multicommodity disconnecting set. multicommodity disconnecting set. multicorte dirigido teoria dos grafos