Título: | ALGORITMOS PARA ACELERAR A COMPUTAÇÃO DE ÁRVORES DE CORTE DE GOMORY E HU | |||||||
Autor: |
JOAO PAULO DE FREITAS ARAUJO |
|||||||
Colaborador(es): |
MADIAGNE DIALLO - Orientador |
|||||||
Catalogação: | 19/AGO/2011 | Língua(s): | PORTUGUÊS - BRASIL |
|||||
Tipo: | TEXTO | Subtipo: | TESE | |||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
|||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=18109&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=18109&idi=2 |
|||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.18109 | |||||||
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.
|
||||||||