Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-14T02:44:48Z (GMT). No. of bitstreams: 1
Silva_GustavoPeixoto_M.pdf: 1810173 bytes, checksum: a1944ac8ac4c940f289c30c233c64387 (MD5)
Previous issue date: 1992 / 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. / Mestrado / Mestre em Matemática Aplicada
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/306874 |
| Date | 24 February 1992 |
| Creators | Silva, Gustavo Peixoto |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Perin Filho, Clovis, 1947- |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Matemática Aplicada |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | [70]f. : il., application/pdf |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds