Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/4102
Title: An algorithm for ranking quickest simple paths
Authors: Pascoal, Marta M. B. 
Captivo, M. Eugénia V. 
Clímaco, João C. N. 
Keywords: Graph theory; Network; Quickest path; Simple path; Paths ranking
Issue Date: 2005
Citation: Computers & Operations Research. 32:3 (2005) 509-520
Abstract: 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.
URI: http://hdl.handle.net/10316/4102
Rights: openAccess
Appears in Collections:FEUC- Artigos em Revistas Internacionais
FCTUC Eng.Informática - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
file93575488f5ae462fb81c859da64d03dc.pdf278.22 kBAdobe PDFView/Open
Show full item record

Page view(s) 50

441
checked on Jul 9, 2020

Download(s)

165
checked on Jul 9, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.