Um sistema distribuído para busca de caminhos em grafos dinâmicos
Resumo
Este trabalho descreve um novo modelo para cálculo concorrente de caminhos em grafos dinâmicos os quais podem estar particionados em um conjunto de servidores interconectados. Aspectos dinâmicos em cálculos de caminhos têm sido bem explorados em trabalhos anteriores, neste trabalho, consideramos também aspectos de distribuição. O arcabouço proposto pode ser usado com algoritmos de cálculo de caminhos dinâmicos ou estáticos. O modelo pode ser usado em sistemas simulando o estado de uma rede ou o monitormento das condições de trânsito de uma cidade. O artigo também apresenta alguns detalhes de implementação bem como resultados de testes.Referências
T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd. edition, 2001.
J. Fawcett and P. Robinson. Adaptive routing for road traffic. IEEE Computer Graphics and Applications, 20(3):46–53, May/June 2000.
D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Incremental algorithms for single-source shortest path trees. Proceedings of Foundations of Software Technology and Theoretical Computer Science, pages 113–124, December 1994.
V. Garg. Elements of Distributed Computing. John Wiley and Sons, 1st. edition, 2002.
P. Narváez, K. Siu, and H. Tzeng. New dynamic algorithms for shortest path tree computation. IEEE/ACM Transactions on Networking, 8(6):734–746, December 2000.
G. Ramalingam and T. Reps. An incremental algorithm for a generalization of the shortest path problem. Journal of Algorithms, 21:267–305, 1996.
M. Schwartz. Mobile Wireless Communications. Cambridge University Press, 1st. edition, 2005.
J. Fawcett and P. Robinson. Adaptive routing for road traffic. IEEE Computer Graphics and Applications, 20(3):46–53, May/June 2000.
D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Incremental algorithms for single-source shortest path trees. Proceedings of Foundations of Software Technology and Theoretical Computer Science, pages 113–124, December 1994.
V. Garg. Elements of Distributed Computing. John Wiley and Sons, 1st. edition, 2002.
P. Narváez, K. Siu, and H. Tzeng. New dynamic algorithms for shortest path tree computation. IEEE/ACM Transactions on Networking, 8(6):734–746, December 2000.
G. Ramalingam and T. Reps. An incremental algorithm for a generalization of the shortest path problem. Journal of Algorithms, 21:267–305, 1996.
M. Schwartz. Mobile Wireless Communications. Cambridge University Press, 1st. edition, 2005.
Publicado
17/10/2006
Como Citar
VINAGREIRO, Marcelo; GOLDMAN, Alfredo.
Um sistema distribuído para busca de caminhos em grafos dinâmicos. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 7. , 2006, Ouro Preto.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2006
.
p. 81-88.
DOI: https://doi.org/10.5753/wscad.2006.18950.
