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...
| Autor principal: | |
|---|---|
| Outros Autores: | , |
| Formato: | article |
| Idioma: | eng |
| Publicado em: |
2005
|
| Assuntos: | |
| Texto completo: | http://hdl.handle.net/10316/4102 |
| País: | Portugal |
| Oai: | oai:estudogeral.sib.uc.pt:10316/4102 |
| Resumo: | 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. |
|---|