dc.contributor.author | Martins, Geoffrey Alberto Vitorio | pt_BR |
dc.contributor.other | Guedes, Andre Luiz Pires, 1966- | pt_BR |
dc.contributor.other | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | pt_BR |
dc.date.accessioned | 2021-06-07T17:52:09Z | |
dc.date.available | 2021-06-07T17:52:09Z | |
dc.date.issued | 2012 | pt_BR |
dc.identifier.uri | https://hdl.handle.net/1884/35025 | |
dc.description | Orientadores : Prof. Dr. André Luiz Pires Guedes | pt_BR |
dc.description | Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Ciência da Computação. Defesa: Curitiba, 30/08/2011 | pt_BR |
dc.description | Inclui referências | pt_BR |
dc.description.abstract | Resumo: Esse trabalho faz uma análise crítica detalhada de alguns algoritmos de manutenção e consulta em grafos dinâmicos como o algoritmo de Even e Shiloach, o algoritmo de Henzinger e King e em especial o algoritmo de Roditty e Zwick, um algoritmo totalmente dinâmico com propriedades interessantes como critérios para a reinicialização de suas estruturas ou o uso de paralelismo em suas consultas. Além de apresentar o algoritmo e sua análise inicial, uma análise crítica é feita examinando diversos aspectos do algoritmo original, onde são propostas modificações de forma a introduzir melhorias de precisão e desempenho, assim como melhores maneiras de escolher seus conjuntos aleatórios, modificações em suas condições de reinício para aumentar as chances de que o caminho mínimo seja encontrado ou ainda inclusão de funcionalidade adicional. | pt_BR |
dc.description.abstract | Abstract: This work provides a detailed critical analysis of some dynamic graph algorithm, targeting maintenance and queries of shortest paths. Analyzed algorithms includes the Even-Shiloach algorithm, the Henzinger-King Algorithm and as the main focus, the algorithm of Roditty and Zwick, a fully-dynamic all-pairs algorithm with a number of interesting characteristics such as the existence of certain conditions in which a full reinitialization of the structures is performed or the use of parallelism in its query processes. Besides presenting an introduction to the algorithms and the initial analysis, a critical analysis of the Roditty-Zwick algorithm is presented, pointing the strong and weak spots and highlighting some of the more interesting characteristics of the algorithm. Afterwards, a number of changes are proposed, such as better ways to choose its random vertex sets, modifications in the restart conditions or even the addition of new functionality. | pt_BR |
dc.format.extent | 64f. : il. algumas color., grafs., tabs. | pt_BR |
dc.format.mimetype | application/pdf | pt_BR |
dc.language | Português | pt_BR |
dc.relation | Disponível em formato digital | pt_BR |
dc.subject | Teses | pt_BR |
dc.subject | Ciência da Computação | pt_BR |
dc.subject | Teoria dos grafos | pt_BR |
dc.subject | Algorítmos paralelos | pt_BR |
dc.title | Manutenção de caminhos mínimos em grafos dinâmicos | pt_BR |
dc.type | Dissertação | pt_BR |