An algorithm for ranking quickest simple paths

• Autor(es): Pascoal, Marta M. B. ; Captivo, M. Eugénia V. ; Clímaco, João C. N.
• Data: 2005
• Identificador Persistente: http://hdl.handle.net/10316/4102
• Origem: Estudo Geral - Universidade de Coimbra
• Assunto(s): Graph theory; Network; Quickest path; Simple path; Paths ranking
• Tipo de Documento: Artigo
• Idioma: Inglês

Descrição

In this paper, an algorithm for ranking loopless paths in undirected networks, according to the transmission time, is presented. It is shown that the worst-case computational time complexity of the algorithm presented is , which is also the best-known complexity to solve this problem. The worst-case memory complexity is , which improves the existing algorithms. Finally, comparative computational results, with other algorithms for the same problem, are reported. http://www.sciencedirect.com/science/article/B6VC5-49H1010-2/1/2e3e3bf1d27b1f02e63aa36fe9459417