{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:12:00Z","timestamp":1778278320697,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T00:00:00Z","timestamp":1430870400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00453-015-0003-0","type":"journal-article","created":{"date-parts":[[2015,5,5]],"date-time":"2015-05-05T12:43:52Z","timestamp":1430829832000},"page":"1404-1434","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Distance Oracles for Time-Dependent Networks"],"prefix":"10.1007","volume":"74","author":[{"given":"Spyros","family":"Kontogiannis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,6]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, R.: The space-stretch-time trade-off in distance oracles. In: ESA (2014), to appear","DOI":"10.1007\/978-3-662-44777-2_5"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, R., Godfrey, P.: Distance oracles for stretch less than 2. In: SODA 2013, pp. 526\u2013538. ACM-SIAM, (2013)","DOI":"10.1137\/1.9781611973105.38"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Akrida, E., Gasieniec, L., Mertzios, G., Spirakis, P.: Ephemeral networks with random availability of links: diameter and connectivity. In: 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA \u201914), pp. 267\u2013276, (2014)","DOI":"10.1145\/2612669.2612693"},{"key":"3_CR4","first-page":"1","volume":"18","author":"GV Batz","year":"2013","unstructured":"Batz, G.V., Geisberger, R., Sanders, P., Vetter, C.: Minimum time-dependent travel times with contraction hierarchies. ACM J. Exper. Algorithm. 18, 1\u201343 (2013)","journal-title":"ACM J. Exper. Algorithm."},{"issue":"3","key":"3_CR5","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1287\/moor.16.3.580","volume":"16","author":"D Bertsekas","year":"1991","unstructured":"Bertsekas, D., Tsitsiklis, J.: An analysis of stochastic shortest path problems. Math. Oper. Res. 16(3), 580\u2013595 (1991)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"3_CR6","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1016\/0022-247X(66)90009-6","volume":"14","author":"K Cooke","year":"1966","unstructured":"Cooke, K., Halsey, E.: The shortest route through a network with time-dependent intermodal transit times. J. Math. Anal. Appl. 14(3), 493\u2013498 (1966)","journal-title":"J. Math. Anal. Appl."},{"key":"3_CR7","unstructured":"Dean, B.C.: Continuous-time dynamic shortest path algorithms. MSc thesis. MIT, (1999)"},{"issue":"1","key":"3_CR8","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/net.20013","volume":"44","author":"BC Dean","year":"2004","unstructured":"Dean, B.C.: Algorithms for minimum-cost paths in time-dependent networks with waiting policies. Networks 44(1), 41\u201346 (2004)","journal-title":"Networks"},{"key":"3_CR9","unstructured":"Dean, B.C.: Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report, MIT (2004)"},{"issue":"1\u20132","key":"3_CR10","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/s00453-010-9461-6","volume":"62","author":"F Dehne","year":"2012","unstructured":"Dehne, F., Masoud, O.T., Sack, J.R.: Shortest paths in time-dependent fifo networks. Algorithmica 62(1\u20132), 416\u2013435 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"3_CR11","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/s00453-009-9341-0","volume":"60","author":"D Delling","year":"2011","unstructured":"Delling, D.: Time-dependent SHARC-routing. Algorithmica 60(1), 60\u201394 (2011)","journal-title":"Algorithmica"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Delling, D., Wagner, D.: Time-Dependent Route Planning. In: Ahuja, R.K., M\u00f6hring, R.H., Zaroliagis, C. (eds.) Robust and Online Large-Scale Optimization, LNCS 5868, pp. 207\u2013230. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-05465-5_8"},{"key":"3_CR13","unstructured":"Demetrescu, C., Italiano, G.F.: Dynamic shortest paths and transitive closure: an annotated bibliography (draft), (2005). http:\/\/www.diku.dk\/PATH05\/biblio-dynpaths"},{"issue":"3","key":"3_CR14","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"SE 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":"3_CR15","unstructured":"eCOMPASS Project (2011\u20132014). http:\/\/www.ecompass-project.eu"},{"issue":"4","key":"3_CR16","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1007\/s00453-012-9714-7","volume":"68","author":"L Foschini","year":"2014","unstructured":"Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. Algorithmica 68(4), 1075\u20131097 (2014). Prelim. version in SODA 2011","journal-title":"Algorithmica"},{"key":"3_CR17","unstructured":"Gusfield, D.M.: Sensitivity analysis for combinatorial optimization. Phd thesis, University of California, Berkeley, (1980)"},{"key":"3_CR18","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64, 820\u2013842 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proceedings of 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 81\u201389, (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Kontogiannis, S., Zaroliagis, C.: Distance oracles for time dependent networks. In: Automata, Languages and Programming (Track A). Lecture Notes in Computer Science 8572, pp. 713\u2013725. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_59"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Mertzios, G., Michail, O., Chatzigiannakis, I., Spirakis, P.: Temporal Network Optimization Subject to Connectivity Constraints In: Automata, Languages and Programming (Track C). Lecture Notes in Computer Science 7966, pp. 657\u2013668. Springer (2013)","DOI":"10.1007\/978-3-642-39212-2_57"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1006\/jcss.2001.1766","volume":"63","author":"K Mulmuley","year":"2001","unstructured":"Mulmuley, K., Shah, P.: A lower bound for the shortest path problem. J. Compt. Syst. Sci. 63, 253\u2013267 (2001)","journal-title":"J. Compt. Syst. Sci."},{"key":"3_CR23","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1002\/net.20438","volume":"59","author":"G Nannicini","year":"2012","unstructured":"Nannicini, G., Delling, D., Liberti, L., Schultes, D.: Bidirectional A* search on time-dependent road networks. Networks 59, 240\u2013251 (2012)","journal-title":"Networks"},{"key":"3_CR24","unstructured":"Nikolova, E., Brand, M., Karger, D.: Optimal route planning under uncertainty. In: International Conference on Automated Planning and Scheduling, (2006)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Nikolova, E., Kelner, J., Brand, M., Mitzenmacher, M.: Stochastic shortest paths via quasi-convex maximization. In: 14th European Symposium on Algorithms, pp. 552\u2013563, (2006)","DOI":"10.1007\/11841036_50"},{"issue":"3","key":"3_CR26","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":"3_CR27","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Roditty, L.: cDistance oracles beyond the Thorup-Zwick bound. In: IEEE Symposium on Foundations of Computer Science, pp. 815\u2013823, (2010)","DOI":"10.1109\/FOCS.2010.83"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Porat, E., Roditty, L.: Preprocess, set, query! In: European Symposium on Algorithms, LNCS 6942, pp. 603\u2013614. Springer, (2011)","DOI":"10.1007\/978-3-642-23719-5_51"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: On Dynamic Shortest Paths Problems. In: 12th Annual European Symposium on Algorithms. Lecture Notes in Computer Science 3221, pp. 580\u2013591. Springer (2004)","DOI":"10.1007\/978-3-540-30140-0_52"},{"issue":"4","key":"3_CR30","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 Sherali","year":"1998","unstructured":"Sherali, H., 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":"3_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2530531","volume":"46","author":"C Sommer","year":"2014","unstructured":"Sommer, C.: Shortest-path queries in static networks. ACM Comput. Surv. 46, 1\u201331 (2014)","journal-title":"ACM Comput. Surv."},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Sommer, C., Verbin, E., Yu, W.: Distance oracles for sparse graphs. In: IEEE Symposium on Foundations of Computer Science, pp. 703\u2013712, (2009)","DOI":"10.1109\/FOCS.2009.27"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: 37th Annual ACM Symposium on Theory of Computing, pp. 112\u2013119, (2005)","DOI":"10.1145\/1060590.1060607"},{"key":"3_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52, 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Approximate distance oracles with improved preprocessing time. In: SODA 2012. ACM-SIAM, (2012)","DOI":"10.1137\/1.9781611973099.18"},{"key":"3_CR36","unstructured":"Wulff-Nilsen, C.: Approximate distance oracles with improved query time, (2012). arXiv:1202.2336"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0003-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0003-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0003-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,24]],"date-time":"2019-08-24T15:41:10Z","timestamp":1566661270000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0003-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,6]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["3"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0003-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,6]]}}}