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 script O sign (Kr(m+nlogn)), which is also the best-known complexity to solve this problem. The worst-case memory complexity is script O signs (Kn), which improves the existing algorithms. Finally, comparative computational results, with other algorithms for the same problem, are reported. © 2003 Elsevier Ltd. All rights reserved.
An algorithm for ranking quickest simple paths
Pascoal M.;
2005-01-01
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 script O sign (Kr(m+nlogn)), which is also the best-known complexity to solve this problem. The worst-case memory complexity is script O signs (Kn), which improves the existing algorithms. Finally, comparative computational results, with other algorithms for the same problem, are reported. © 2003 Elsevier Ltd. All rights reserved.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
05COR.pdf
Accesso riservato
:
Publisher’s version
Dimensione
278.22 kB
Formato
Adobe PDF
|
278.22 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
