Title :
An Algorithm to Find the kth Shortest Path in Halin Networks
Author :
Lu, Yunting ; Li, Zhenjun
Author_Institution :
Shenzhen Inst. of Inf. Technol., Shenzhen
Abstract :
K shortest path problem finds the kth shortest path from the source node to the destination node. Itpsilas known that the k shortest path problem is NP-complete. In this paper, we restrict the problem in Halin Networks and give an algorithm to find the kth shortest paths. The time complexity is O(k3|V|).
Keywords :
computational complexity; dynamic programming; graph theory; Halin networks; NP-complete problem; destination node; shortest path problem; source node; time complexity; Clocks; Communication networks; Costs; DNA computing; Information technology; Intelligent networks; Joining processes; Robots; Shortest path problem; Tree graphs; Halin network; algorithm; shortest path;
Conference_Titel :
Intelligent Information Technology Application Workshops, 2008. IITAW '08. International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-0-7695-3505-0
DOI :
10.1109/IITA.Workshops.2008.232
