×

Optimal shortest path set problem in undirected graphs. (English) Zbl 1320.90097

Summary: 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\leq l\leq 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)\).

MSC:

90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[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-714 · Zbl 1013.68134
[2] Akgun V, Erkut E, Batta R (2000) On finding dissimilar paths. Eur J Oper Res 121(2):232-246 · Zbl 0951.91050 · doi:10.1016/S0377-2217(99)00214-3
[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-270 · Zbl 0800.68642
[4] Dell’Olmo P, Gentili M, Scozzari A (2007) On finding dissimilar pareto-optimal paths. Eur J Oper Res 162(1):70-82 · Zbl 1132.90303 · doi:10.1016/j.ejor.2003.10.033
[5] Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269-271 · Zbl 0092.16002 · doi:10.1007/BF01386390
[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(4):64 · Zbl 1300.68058 · doi:10.1145/1824777.1824784
[7] Eppstein D (1998) Finding the \[k\] k shortest paths. SIAM J Comput 28(2):652-673 · Zbl 0912.05057 · doi:10.1137/S0097539795290477
[8] Fredman M, Tarjan R (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J ACM 34(3):596-615 · Zbl 1412.68048 · doi:10.1145/28869.28874
[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-259 · Zbl 0092.16002
[10] Katoh N, Ibaraki T, Mine H (1982) An efficient algorithm for K shortest simple paths. Networks 12(4):411-427 · Zbl 0493.68068 · doi:10.1002/net.3230120406
[11] Malik K, Mittal Ak, Gupta Sk (1989) The \[k\] k most vital arcs in the shortest path problem. Oper Res Lett 8(4):223-227 · Zbl 0669.90090 · doi:10.1016/0167-6377(89)90065-5
[12] Nardelli E, Proietti G, Widmayer P (1998) Finding the detour-critical edge of a shortest path between two nodes. Inform Process Lett 67(1):51-54 · Zbl 1339.68210 · doi:10.1016/S0020-0190(98)00077-5
[13] Nardelli E, Proiett G, Widmayer P (2001) A faster computation of the most vital edge of a shortest path. Info Process Lett 79(2):81-85 · Zbl 1013.68134 · doi:10.1016/S0020-0190(00)00175-7
[14] Wulff-Nilsen C (2010) Solving the replacement paths problem for planar directed graphs in \[O(n \log n)O\](nlogn) time. In: Proceedings of the 21th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp 756-765 · Zbl 1288.68279
[15] Xiao P, Xu Y, Su B (2009) Finding an anti-risk path between two nodes in undirected graphs. J Comb Optim 17(3):235-246 · Zbl 1180.90352 · doi:10.1007/s10878-007-9110-4
[16] Xu Y, Hu M, Su B, Zhu B, Zhu Z (2009) The Canadian traveller problem and its competitive analysis. J Comb Optim 18(2):195-205 · Zbl 1173.90524 · doi:10.1007/s10878-008-9156-y
[17] Yen JY (1971) Finding the K shortest loopless paths in a network. Manag Sci 17:712-716 · Zbl 0218.90063 · doi:10.1287/mnsc.17.11.712
[18] Zhang H, Xu Y, Qin L (2013) The \[k\] k-Canadian travelers problem with communication. J Comb Optim 26(2):251-265 · Zbl 1275.90085 · doi:10.1007/s10878-012-9503-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.