Manutenção de caminhos mínimos em grafos dinâmicos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorGuedes, Andre Luiz Pires, 1966--
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática-
Autor(es): dc.creatorMartins, Geoffrey Alberto Vitorio-
Data de aceite: dc.date.accessioned2019-08-21T23:03:16Z-
Data de disponibilização: dc.date.available2019-08-21T23:03:16Z-
Data de envio: dc.date.issued2015-12-02-
Data de envio: dc.date.issued2015-12-02-
Data de envio: dc.date.issued2012-
Fonte completa do material: dc.identifierhttp://hdl.handle.net/1884/35025-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/35025-
Descrição: dc.descriptionOrientadores : Prof. Dr. André Luiz Pires Guedes-
Descrição: dc.descriptionDissertaçã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-
Descrição: dc.descriptionInclui referências-
Descrição: dc.descriptionResumo: 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.-
Descrição: dc.descriptionAbstract: 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.-
Formato: dc.format64f. : il. algumas color., grafs., tabs.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Relação: dc.relationDisponível em formato digital-
Palavras-chave: dc.subjectTeses-
Palavras-chave: dc.subjectComputação-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectAlgoritmos paralelos-
Título: dc.titleManutenção de caminhos mínimos em grafos dinâmicos-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.