Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306874
Type: TESE
Title: Um estudo do algoritmo de Goldberg e Tarjan para o problema de luxo maximo
Author: Silva, Gustavo Peixoto
Advisor: Perin Filho, Clovis, 1947-
Filho, Clovis Perin
Abstract: Resumo: Este trabalho consiste no estudo e na implementação do algoritmo de Goldberg e Tarjan para o problema' do fluxo máximo. Este algoritmo tem destacada importância por apresentar uma das complexidades mais baixas e também pelo fato de abordar o problema de maneira diferenciada. Goldberg e Tarjan utilizam a estrutura de dados árvores dinâmicas para atingir a complexidade O(nm log(n2/m)) numa rede n-nós, m-arcos. Em redes densas (m = O (n2)) a complexidade deste algoritmo é tão boa quanto qualquer outro algoritmo, tendo uma das melhores complexidades em redes de densidade moderada. (m = O(n3/2)). Este algoritmo apresenta duas versões, uma que não utiliza a estrutura de dados árvores dinâmicas e tem complexidade O(n3), e outra versão que incorpora ao algoritmo anterior as árvores dinâmicas, conseguindo a complexidade de O(nm log(n2 1m)). Foram realizados testes comparativos com as duas versões e os principais al&oritmos conhecidos para o problema, tendo em vista o tempo de CPU em cada método. As redes utilizadas neste trabalho têm características particulares.

Abstract: Not informed.
Subject: Algoritmos
Programação (Matemática)
Language: Português
Editor: [s.n.]
Date Issue: 1992
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Silva_GustavoPeixoto_M.pdf1.77 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.