Optimal shortest path set problem in undirected graphs

详细信息    查看全文

• 作者：Huili Zhang (1) (2)
  Yinfeng Xu (1) (2)
  Xingang Wen (1) (2)
  
  1. School of Management ; Xi鈥檃n Jiaotong University ; Xi鈥檃n ; 710049 ; China
  2. State Key Lab for Manufacturing Systems Engineering ; Xi鈥檃n ; 710049 ; China
  
• 关键词：Shortest path ; Common replacement path ; Optimal shortest path set ; Time complexity
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：29
• 期：3
• 页码：511-530
• 全文大小：801 KB
• 参考文献：1. Adhari H, Dreibholz T, Becke M (2011) Evaluation of concurrent multipath transfer over dissimilar paths. In: Proceedings of the 25th IEEE International Conference on Advanced Information Networking and Applications Workshops (WAINA) pp 708鈥?14
  2. Akgun, V, Erkut, E, Batta, R (2000) On finding dissimilar paths. Eur J Oper Res 121: pp. 232-246 CrossRef
  3. Bar-Noy A, Schieber B (1991) The canadian traveller problem. In: Proceedings of the second annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, pp 261鈥?70
  4. Dell鈥橭lmo, P, Gentili, M, Scozzari, A (2007) On finding dissimilar pareto-optimal paths. Eur J Oper Res 162: pp. 70-82 CrossRef
  5. Dijkstra, EW (1959) A note on two problems in connexion with graphs. Numer Math 1: pp. 269-271 CrossRef
  6. Emek, Y, Peleg, D, Rodity, L (2010) A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Trans Algorithms 6: pp. 64 CrossRef
  7. Eppstein, D (1998) Finding the $$k$$ k shortest paths. SIAM J Comput 28: pp. 652-673 CrossRef
  8. Fredman, M, Tarjan, R (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J ACM 34: pp. 596-615 CrossRef
  9. Hershberger J, Suri S (2001) Vickrey prices and shortest paths: what is an edge worth?. In: Proceedings of the 42nd IEEE Annual Symposium on Foundations of Computer Science (FOCS01) pp 252鈥?59
  10. Katoh, N, Ibaraki, T, Mine, H (1982) An efficient algorithm for K shortest simple paths. Networks 12: pp. 411-427 CrossRef
  11. Malik, K, Mittal, Ak, Gupta, Sk (1989) The $$k$$ k most vital arcs in the shortest path problem. Oper Res Lett 8: pp. 223-227 CrossRef
  12. Nardelli, E, Proietti, G, Widmayer, P (1998) Finding the detour-critical edge of a shortest path between two nodes. Inform Process Lett 67: pp. 51-54 CrossRef
  13. Nardelli, E, Proiett, G, Widmayer, P (2001) A faster computation of the most vital edge of a shortest path. Info Process Lett 79: pp. 81-85 CrossRef
  14. Wulff-Nilsen C (2010) Solving the replacement paths problem for planar directed graphs in \(O(n \log n)\) time. In: Proceedings of the 21th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp 756鈥?65
  15. Xiao, P, Xu, Y, Su, B (2009) Finding an anti-risk path between two nodes in undirected graphs. J Comb Optim 17: pp. 235-246 CrossRef
  16. Xu, Y, Hu, M, Su, B, Zhu, B, Zhu, Z (2009) The Canadian traveller problem and its competitive analysis. J Comb Optim 18: pp. 195-205 CrossRef
  17. Yen, JY (1971) Finding the K shortest loopless paths in a network. Manag Sci 17: pp. 712-716 CrossRef
  18. Zhang, H, Xu, Y, Qin, L (2013) The $$k$$ k -Canadian travelers problem with communication. J Comb Optim 26: pp. 251-265 CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

This paper proposes the optimal shortest path set problem in an undirected graph \(G=(V,E)\) , in which some vehicles have to go from a source node \(s\) to a destination node \(t\) . However, at most \(k\) edges in the graph may be blocked during the traveling. The goal is to find a minimum collection of paths for the vehicles before they start off to assure the fastest arrival of at least one vehicle, no matter which \(l\) \((0\le l\le k)\) edges are blocked. We consider two scenarios for this problem. In the first scenario with \(k=1\) , we propose the concept of common replacement path and design the Least-Overlap Algorithm to find the common replacement path. Based on this, an algorithm to compute the optimal shortest path set is presented and its time complexity is proved to be \(O(n^2)\) . In the second scenario with \(k>1\) , we consider the case where the blocked edges are consecutive ones on a shortest path from \(s\) to \(t\) and the vertices connecting two blocked edges are also blocked (i.e., routes passing through these vertices are not allowed), and an algorithm is presented to compute the optimal shortest path set in this scenario with time complexity \(O(mn+k^2n^2\log n)\) .