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

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.

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.