{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T06:19:49Z","timestamp":1780467589121,"version":"3.54.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,11,18]],"date-time":"2012-11-18T00:00:00Z","timestamp":1353196800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00453-012-9714-7","type":"journal-article","created":{"date-parts":[[2012,11,17]],"date-time":"2012-11-17T10:07:49Z","timestamp":1353146869000},"page":"1075-1097","source":"Crossref","is-referenced-by-count":64,"title":["On the Complexity of Time-Dependent Shortest Paths"],"prefix":"10.1007","volume":"68","author":[{"given":"Luca","family":"Foschini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,11,18]]},"reference":[{"key":"9714_CR1","first-page":"747","volume-title":"Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Basch","year":"1997","unstructured":"Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. In: Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 747\u2013756 (1997)"},{"issue":"3","key":"9714_CR2","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1287\/moor.16.3.580","volume":"16","author":"D.P. Bertsekas","year":"1991","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: An analysis of stochastic shortest path problems. Math. Oper. Res. 16(3), 580\u2013595 (1991)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9714_CR3","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO;2-H","volume":"29","author":"X. Cai","year":"1997","unstructured":"Cai, X., Kloks, T., Wong, C.K.: Time-varying shortest path problems with constraints. Networks 29(3), 141\u2013150 (1997)","journal-title":"Networks"},{"key":"9714_CR4","unstructured":"Carstensen, P.J.: Parametric cost shortest path problems (1984). Unpublished Bellcore memo"},{"key":"9714_CR5","doi-asserted-by":"crossref","first-page":"170","DOI":"10.3141\/1645-21","volume":"1645","author":"I. Chabini","year":"1998","unstructured":"Chabini, I.: Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time. J. Transp. Res. Board. 1645, 170\u2013175 (1998)","journal-title":"J. Transp. Res. Board."},{"key":"9714_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, New York (2001)","edition":"2"},{"key":"9714_CR7","unstructured":"Dean, B.C.: Continuous-time dynamic shortest path algorithms. Master\u2019s thesis, Massachusetts Institute of Technology (1999)"},{"key":"9714_CR8","unstructured":"Dean, B.C.: Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report (2004)"},{"key":"9714_CR9","first-page":"1","volume-title":"Proc. of 2nd International Workshop on Computational Transportation Science","author":"F. Dehne","year":"2009","unstructured":"Dehne, F., Omran, M.T., Sack, J.-R.: Shortest paths in time-dependent FIFO networks using edge load forecasts. In: Proc. of 2nd International Workshop on Computational Transportation Science, pp. 1\u20136 (2009)"},{"key":"9714_CR10","doi-asserted-by":"crossref","unstructured":"Dehne, F., Omran, M.T., Sack, J.R.: Shortest paths in time-dependent FIFO networks. Algorithmica, 1\u201320 (2010)","DOI":"10.1007\/s00453-010-9461-6"},{"key":"9714_CR11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-642-05465-5_8","volume-title":"Robust and Online Large-Scale Optimization","author":"D. Delling","year":"2009","unstructured":"Delling, D., Wagner, D.: Time-dependent route planning. In: Robust and Online Large-Scale Optimization, vol. 5868, pp. 207\u2013230 (2009)"},{"key":"9714_CR12","unstructured":"Demetrescu, C., Italiano, G.F.: Dynamic shortest paths and transitive closure: An annotated bibliography (draft) (2005). See www.diku.dk\/PATH05\/biblio-dynpaths.pdf"},{"key":"9714_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/1353343.1353371","volume-title":"Proc. of the 11th International Conference on Extending Database Technology","author":"B. Ding","year":"2008","unstructured":"Ding, B., Yu, J.X., Qin, L.: Finding time-dependent shortest paths over large graphs. In: Proc. of the 11th International Conference on Extending Database Technology, pp. 205\u2013216 (2008)"},{"issue":"3","key":"9714_CR14","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"S.E. Dreyfus","year":"1969","unstructured":"Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395\u2013412 (1969)","journal-title":"Oper. Res."},{"key":"9714_CR15","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1137\/1.9781611973075.65","volume-title":"Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Erickson","year":"2010","unstructured":"Erickson, J.: Maximum flows and parametric shortest paths in planar graphs. In: Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 794\u2013804 (2010)"},{"issue":"3","key":"9714_CR16","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1006\/jagm.1994.1019","volume":"16","author":"D. Fern\u00e1ndez-Baca","year":"1994","unstructured":"Fern\u00e1ndez-Baca, D., Slutzki, G.: Parametric problems on graphs of bounded tree-width. J. Algorithms 16(3), 408\u2013430 (1994)","journal-title":"J. Algorithms"},{"key":"9714_CR17","volume-title":"Flows in Networks","author":"L.R. Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"9714_CR18","first-page":"191","volume-title":"Proc. of the Workshop on Algorithmic Foundations of Robotics","author":"L.J. Guibas","year":"1998","unstructured":"Guibas, L.J.: Kinetic data structures\u2014a state of the art report. In: Agarwal, P.K., Kavraki, L.E., Mason, M. (eds.) Proc. of the Workshop on Algorithmic Foundations of Robotics, pp. 191\u2013209 (1998)"},{"key":"9714_CR19","unstructured":"Gusfield, D.M.: Sensitivity analysis for combinatorial optimization. PhD thesis, University of California, Berkeley (1980)"},{"key":"9714_CR20","first-page":"10","volume-title":"Proc. of the 22nd International Conference on Data Engineering","author":"E. Kanoulas","year":"2006","unstructured":"Kanoulas, E., Du, Y., Xia, T., Zhang, D.: Finding fastest paths on a road network with speed patterns. In: Proc. of the 22nd International Conference on Data Engineering, p. 10 (2006)"},{"issue":"1","key":"9714_CR21","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","volume":"3","author":"R.M. Karp","year":"1981","unstructured":"Karp, R.M., Orlin, J.B.: Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math. 3(1), 37\u201345 (1981)","journal-title":"Discrete Appl. Math."},{"key":"9714_CR22","first-page":"81","volume-title":"Proc. of the 40th Annual Symposium on Foundations of Computer Science","author":"V. King","year":"1999","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. of the 40th Annual Symposium on Foundations of Computer Science, pp. 81\u201389 (1999)"},{"issue":"1","key":"9714_CR23","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/102782.102784","volume":"38","author":"J.S.B. Mitchell","year":"1991","unstructured":"Mitchell, J.S.B., Papadimitriou, C.H.: The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM 38(1), 18\u201373 (1991)","journal-title":"J. ACM"},{"key":"9714_CR24","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/CCC.2000.856731","volume-title":"Proc. of the 15th Annual IEEE Conference on Computational Complexity","author":"K. Mulmuley","year":"2000","unstructured":"Mulmuley, K., Shah, P.: A lower bound for the shortest path problem. In: Proc. of the 15th Annual IEEE Conference on Computational Complexity, pp. 14\u201321 (2000)"},{"issue":"1","key":"9714_CR25","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0377-2217(94)E0349-G","volume":"83","author":"K. Nachtigall","year":"1995","unstructured":"Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1), 154\u2013166 (1995)","journal-title":"Eur. J. Oper. Res."},{"key":"9714_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/978-3-540-68552-4_25","volume-title":"Workshop on Experimental Algorithms","author":"G. Nannicini","year":"2008","unstructured":"Nannicini, G., Delling, D., Liberti, L., Schultes, D.: Bidirectional A \u2217 search for time-dependent fast paths. In: Workshop on Experimental Algorithms. Lecture Notes in Computer Science, vol. 5038, pp. 334\u2013346 (2008)"},{"key":"9714_CR27","volume-title":"Proc. of International Conference on Automated Planning and Scheduling","author":"E. Nikolova","year":"2006","unstructured":"Nikolova, E., Brand, M., Karger, D.R.: Optimal route planning under uncertainty. In: Proc. of International Conference on Automated Planning and Scheduling (2006)"},{"key":"9714_CR28","first-page":"552","volume-title":"Proc. of 14th European Symposium on Algorithms","author":"E. Nikolova","year":"2006","unstructured":"Nikolova, E., Kelner, J.A., Brand, M., Mitzenmacher, M.: Stochastic shortest paths via quasi-convex maximization. In: Proc. of 14th European Symposium on Algorithms, pp. 552\u2013563 (2006)"},{"issue":"3","key":"9714_CR29","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/79147.214078","volume":"37","author":"A. Orda","year":"1990","unstructured":"Orda, A., Rom, R.: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3), 607\u2013625 (1990)","journal-title":"J. ACM"},{"key":"9714_CR30","first-page":"580","volume-title":"Proc. of 12th Annual European Symposium on Algorithms","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Proc. of 12th Annual European Symposium on Algorithms, vol. 3221, pp. 580\u2013591 (2004)"},{"issue":"4","key":"9714_CR31","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1002\/(SICI)1097-0037(199807)31:4<259::AID-NET6>3.0.CO;2-C","volume":"31","author":"H.D. Sherali","year":"1998","unstructured":"Sherali, H.D., Ozbay, K., Subramanian, S.: The time-dependent shortest pair of disjoint paths problem: complexity, models, and algorithms. Networks 31(4), 259\u2013272 (1998)","journal-title":"Networks"},{"key":"9714_CR32","first-page":"112","volume-title":"Proc. of the 37th Annual ACM Symposium on Theory of Computing","author":"M. Thorup","year":"2005","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing, pp. 112\u2013119 (2005)"},{"issue":"2","key":"9714_CR33","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/net.3230210206","volume":"21","author":"N. Young","year":"2006","unstructured":"Young, N., Tarjan, R., Orlin, J.: Faster parametric shortest path and minimum balance algorithms. Networks 21(2), 205\u2013221 (2006)","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9714-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9714-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9714-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T14:29:06Z","timestamp":1643639346000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9714-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,18]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9714"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9714-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,18]]}}}