An algorithm for ranking quickest simple paths

• Author(s): Pascoal, Marta M. B. ; Captivo, M. Eugénia V. ; Clímaco, João C. N.
• Date: 2005
• Persistent ID: http://hdl.handle.net/10316/4102
• Origin: Estudo Geral - Universidade de Coimbra
• Subject(s): Graph theory; Network; Quickest path; Simple path; Paths ranking
• Document Type: Article
• Language: English

Description

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