A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs

详细信息    查看全文

• 作者：Kuo-Hua Kao (1)
  Jou-Ming Chang (2)
  Yue-Li Wang (3) ylwang@cs.ntust.edu.tw
  Justie Su-Tzu Juan (1)
• 关键词：Strictly ; second ; shortest paths &#8211 ; Next ; to ; shortest paths &#8211 ; Graph algorithms
• 刊名：Algorithmica
• 出版年：2011
• 出版时间：October 2011
• 年：2011
• 卷：61
• 期：2
• 页码：402-418
• 全文大小：1,021.7 KB
• 参考文献：1. Barman, S.C., Mondal, S., Pal, M.: An efficient algorithm to find next-to-shortest path on trapezoid graphs. Adv. Appl. Math. Anal. 2, 97–107 (2007)
  2. Dijkstra, E.W.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959)
  3. Krasiko, I., Noble, S.D.: Finding next-to-shortest paths in a graph. Inf. Process. Lett. 92, 117–119 (2004)
  4. Lalgudi, K.N., Papaefthymiou, M.C.: Computing strictly-second shortest paths. Inf. Process. Lett. 63, 177–181 (1997)
  5. Li, S., Sun, G., Chen, G.: Improved algorithm for finding next-to-shortest paths. Inf. Process. Lett. 99, 192–194 (2006)
  6. Mondal, S., Pal, M.: A sequential algorithm to solve next-to-shortest path problem on circular-arc graphs. J. Phys. Sci. 10, 201–217 (2006)
  7. Tarjan, R.: Finding dominators in directed graphs. SIAM J. Comput. 3, 62–89 (1974)
• 作者单位：1. Department of Computer Science and Information Engineering, National Chi Nan University, Nantou, Taiwan, ROC2. Institute of Information Science and Management, National Taipei College of Business, Taipei, Taiwan, ROC3. Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, ROC
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

Given an edge-weighted undirected graph G and two prescribed vertices u and v, a next-to-shortest (u,v)-path is a shortest (u,v)-path amongst all (u,v)-paths having length strictly greater than the length of a shortest (u,v)-path. In this paper, we deal with the problem of computing a next-to-shortest (u,v)-path. We propose an O(n2){\mathcal{O}}(n^{2}) time algorithm for solving this problem, which significantly improves the bound of a previous one in O(n3){\mathcal{O}}(n^{3}) time where n is the number of vertices in G.