An algorithm for ranking quickest simple paths

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...

Full description

Bibliographic Details
Main Author: Pascoal, Marta M. B. (author)
Other Authors: Captivo, M. Eugénia V. (author), Clímaco, João C. N. (author)
Format: article
Language:eng
Published: 2005
Subjects:
Online Access:http://hdl.handle.net/10316/4102
Country:Portugal
Oai:oai:estudogeral.sib.uc.pt:10316/4102
Description
Summary: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.