Abstract
The restricted shortest path (RSP) problem on directed networks is a well-studied problem, and has a large number of applications such as in Quality of Service routing. The problem is known to be NP-hard. In certain cases, however, the network is not static i.e., edge parameters vary over time. In light of this, we extend the RSP problem for general networks to that for temporal networks. We present several exact algorithms for this problem, one of which uses heuristics, and is similar to the \(A^*\) algorithm. We experimentally evaluate these algorithms by simulating them on both existing temporal networks, and synthetic ones. Furthermore, based on one of the pseudo-polynomial exact algorithms, we derive a fully polynomial time approximation scheme.
This research is funded in part by National Science Foundation (NSF) Grants CCF 1218904 and CCF 1527435.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cai, X., Kloks, T., Wong, C.K.: Time-varying shortest path problems with constraints. Networks 29(3), 141–150 (1997)
Carlyle, W.M., Royset, J.O., Kevin Wood, R.: Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks 52(4), 256–270 (2008)
Day, P.R., Ryan, D.M.: Flight attendant rostering for short-haul airline operations. Oper. Res. 45(5), 649–661 (1997)
Ergun, F., Sinha, R., Zhang, L.: An improved FPTAS for restricted shortest path. Inf. Process. Lett. 83(5), 287–291 (2002)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York (1979)
Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 156–165. Society for Industrial and Applied Mathematics, Philadelphia (2005)
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Hassin, R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17(1), 36–42 (1992)
Kempe, D., Kleinberg, J.M., Demers, A.J.: Spatial gossip and resource location protocols. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Crete, Greece, 6–8 July 2001, pp. 163–172 (2001)
Korkmaz, T., Krunz, M.: Multi-constrained optimal path selection. In: Proceedings IEEE INFOCOM 2001, The Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Twenty Years into the Communications Odyssey, Anchorage, Alaska, USA, 22–26 April 2001, pp. 834–843 (2001)
Li, Y., Harms, J., Holte, R.: Fast exact multiconstraint shortest path algorithms. In: IEEE International Conference on Communications, ICC 2007, June 2007, pp. 123–130 (2007)
Lorenz, D., Orda, A.: QoS routing in networks with uncertain parameters. IEEE/ACM Trans. Netw. 6(6), 768–778 (1998)
Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28(5), 213–219 (2001)
Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013)
Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 553–564. Springer, Heidelberg (2014)
Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1), 154–166 (1995)
Van Mieghem, P., Kuipers, F.: Concepts of exact QoS routing algorithms. IEEE/ACM Trans. Netw. 12(5), 851–864 (2004)
Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. Proc. VLDB Endow. 7(9), 721–732 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Biswas, S., Ganguly, A., Shah, R. (2015). Restricted Shortest Path in Temporal Graphs. In: Chen, Q., Hameurlain, A., Toumani, F., Wagner, R., Decker, H. (eds) Database and Expert Systems Applications. Globe DEXA 2015 2015. Lecture Notes in Computer Science(), vol 9261. Springer, Cham. https://doi.org/10.1007/978-3-319-22849-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-22849-5_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22848-8
Online ISBN: 978-3-319-22849-5
eBook Packages: Computer ScienceComputer Science (R0)