• DocumentCode
    690332
  • 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
  • fYear
    2013
  • fDate
    14-15 Dec. 2013
  • Firstpage
    241
  • Lastpage
    244
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computer Sciences and Applications (CSA), 2013 International Conference on
  • Conference_Location
    Wuhan
  • Type

    conf

  • DOI
    10.1109/CSA.2013.62
  • Filename
    6835589
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=690332