DocumentCode
2131040
Title
Finding all hops k-shortest paths
Author
Cheng, Gang ; Ansari, Nitwan
Author_Institution
Dept. of Electr. & Comput. Eng., New Jersey Inst. of Technol., Newark, NJ, USA
Volume
1
fYear
2003
fDate
28-30 Aug. 2003
Firstpage
474
Abstract
In this paper, we introduce and investigate a new problem referred to as the all hops k-shortest paths (AHKP) problem. An efficient solution, the all hops k-shortest paths extended Bellman-Ford (AHKPEB) algorithm, is proposed. Especially, when k = 1, AHKPEB is an optimal comparison-based solution to the all hops optimal path (AHOP) problem in terms of the worst-case computational complexity, i.e., it is impossible to find another comparison-based solution to add-AHOP having the worst-case computational complexity lower than that of AHKPEB.
Keywords
computational complexity; quality of service; telecommunication network routing; QoS routing; all hops k-shortest paths extended Bellman-Ford algorithm; all hops k-shortest paths problem; all hops optimal path problem; optimal comparison-based solution; quality of service; worst-case computational complexity; Computational complexity; Computer networks; Cost function; Educational technology; Gold; Quality of service; Routing;
fLanguage
English
Publisher
ieee
Conference_Titel
Communications, Computers and signal Processing, 2003. PACRIM. 2003 IEEE Pacific Rim Conference on
Print_ISBN
0-7803-7978-0
Type
conf
DOI
10.1109/PACRIM.2003.1235819
Filename
1235819
Link To Document