ALGORITHMS FOR PERFORMING THE COMPUTATION OF GOMORY HU CUT-TREES / ALGORITMOS PARA ACELERAR A COMPUTAÇÃO DE ÁRVORES DE CORTE DE GOMORY E HU

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

13/04/2011

RESUMO

O problema do fluxo máximo multiterminal é uma extensão do conhecido problema de fluxo máximo entre um nó origem e um nó destino de uma rede. Este problema surge no contexto de fluxos em redes, tema que possui diversas aplicações, especialmente nos campos de transporte, telecomunicações e energia. No caso multiterminal, o fluxo máximo é calculado entre todos os pares de nós da rede. No referente a uma rede simétrica, este problema pode ser resolvido, obviamente, pela execução do algoritmo de fluxo máximo n(n ¿ 1) 2 vezes, onde n é o número de nós da rede. Os tradicionais métodos encontrados na literatura o conseguem com apenas n ¿ 1. O presente trabalho busca elaborar um algoritmo capaz de resolver o problema multiterminal com uma complexidade menor do que os métodos da literatura. A recente teoria da análise de sensibilidade, em que se estuda a influência da variação de capacidade de uma aresta nos fluxos máximos multiterminais, é utilizada para a construção do algoritmo. Técnicas dos tradicionais métodos, como a de contração de nós, também compõem o método. Ao final, o algoritmo é testado computacionalmente com todas as suas variações e heurísticas adicionadas. Para um determinado caso, o algoritmo se mostrou com eficiência semelhante a dos métodos tradicionais. Novas variações e heurísticas são listadas para futuras pesquisas.

ASSUNTO(S)

sensibilidade sensitivity fluxos em redes network flows analise analyses arvores trees minimo minimum

ACESSO AO ARTIGO

Documentos Relacionados