Title :
An Algorithm for K Vertices-Constrained Shortest Paths
Author :
Sun Gangming ; Wang Pin
Author_Institution :
Math. & Comput. Sci. Dept., Guangxi Coll. of Educ. Nanning, Nanning, China
Abstract :
An algorithm to find the first k shortest pahtes whose number of vertices are less or equal to m. In an undirected graph with n vertices and w edges, if loops are allowed in the pahtes, the algorithm´s running time is O(2(w+n log2 n)+nw+kwlog2 k). If loops are not allowed, the algorithm´s running time is is O(km((w+nlog2n)+mw)+kwlog2k).
Keywords :
computational complexity; graph theory; algorithm running time; k vertices-constrained shortest paths; undirected graph; Algorithm design and analysis; Arrays; Computers; Educational institutions; Sun; Time complexity; Dijkstra algorithm; branch and bound; constraint; shortest path;
Conference_Titel :
Computer Sciences and Applications (CSA), 2013 International Conference on
Conference_Location :
Wuhan
DOI :
10.1109/CSA.2013.62
