{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T06:31:00Z","timestamp":1763620260617,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,1,11]],"date-time":"2017-01-11T00:00:00Z","timestamp":1484092800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021 138117\/1"],"award-info":[{"award-number":["200021 138117\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["288094"],"award-info":[{"award-number":["288094"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["247073"],"award-info":[{"award-number":["247073"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00224-016-9747-4","type":"journal-article","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T23:50:45Z","timestamp":1484092245000},"page":"600-621","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Computing and Listing st-Paths in Public Transportation Networks"],"prefix":"10.1007","volume":"62","author":[{"given":"Kate\u0159ina","family":"B\u00f6hmov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"H\u00e4fliger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mat\u00fa\u0161","family":"Mihal\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Pr\u00f6ger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gustavo","family":"Sacomoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marie-France","family":"Sagot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,11]]},"reference":[{"unstructured":"Bast, H., Delling, D., Goldberg, A.V., M\u00fcller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route planning in transportation networks (2015). CoRR arXiv: 1504.05140","key":"9747_CR1"},{"unstructured":"Bezem, G., Leeuwen, J.V.: Enumeration in graphs. Tech. Rep. RUU-CS-87-07. Utrecht University (1987)","key":"9747_CR2"},{"doi-asserted-by":"crossref","unstructured":"Birmel\u00e9, E., Ferreira, R.A., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., Sacomoto, G.: Optimal listing of cycles and st-paths in undirected graphs. In: SODA 2013, pp. 1884\u20131896 (2013)","key":"9747_CR3","DOI":"10.1137\/1.9781611973105.134"},{"unstructured":"B\u00f6hmov\u00e1, K., Mihal\u00e1k, M., Neubert, P., Pr\u00f6ger, T., Widmayer, P.: Robust routing in urban public transportation: Evaluating strategies that learn from the past. In: ATMOS 2015, pp. 68\u201381 (2015)","key":"9747_CR4"},{"doi-asserted-by":"crossref","unstructured":"B\u00f6hmov\u00e1, K., Mihal\u00e1k, M., Pr\u00f6ger, T., Sacomoto, G., Sagot, M.: Computing and listing st-paths in public transportation networks. In: CSR 2016, pp. 102\u2013116 (2016)","key":"9747_CR5","DOI":"10.1007\/978-3-319-34171-2_8"},{"unstructured":"B\u00f6hmov\u00e1, K., Mihal\u00e1k, M., Pr\u00f6ger, T., \u0160r\u00e1mek, R., Widmayer, P.: Robust routing in urban public transportation: How to find reliable journeys based on past observations. In: ATMOS 2013, pp. 27\u201341 (2013)","key":"9747_CR6"},{"unstructured":"B\u00f6hmov\u00e1, K., Mihal\u00e1k, M., Pr\u00f6ger, T., Widmayer, P.: Modelling urban public transportation networks to support robust routing. In: CASPT 2015 (2015)","key":"9747_CR7"},{"key":"9747_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.entcs.2003.12.019","volume":"92","author":"GS Brodal","year":"2004","unstructured":"Brodal, G.S., Jacob, R.: Time-dependent networks as models to achieve fast exact time-table queries. Electr. Notes Theor. Comput. Sci 92, 3\u201315 (2004)","journal-title":"Electr. Notes Theor. Comput. Sci"},{"issue":"11","key":"9747_CR9","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1145\/363269.363610","volume":"12","author":"RB Dial","year":"1969","unstructured":"Dial, R.B.: Algorithm 360: shortest-path forest with topological ordering. Commun. ACM 12(11), 632\u2013633 (1969)","journal-title":"Commun. ACM"},{"issue":"1","key":"9747_CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269\u2013271 (1959)","journal-title":"Numer. Math."},{"doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC 2014, pp. 624\u2013633 (2014)","key":"9747_CR11","DOI":"10.1145\/2591796.2591884"},{"doi-asserted-by":"crossref","unstructured":"Disser, Y., M\u00fcller-Hannemann, M., Schnee, M.: Multi-criteria shortest paths in time-dependent train networks. In: WEA 2008, pp. 347\u2013361 (2008)","key":"9747_CR12","DOI":"10.1007\/978-3-540-68552-4_26"},{"issue":"2","key":"9747_CR13","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D Eppstein","year":"1998","unstructured":"Eppstein, D.: Finding the k shortest paths. SIAM J. Comput. 28(2), 652\u2013673 (1998)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Firmani, D., Italiano, G.F., Laura, L., Santaroni, F.: Is timetabling routing always reliable for public transport? In: ATMOS 2013, pp. 15\u201326 2013. doi: 10.4230\/OASIcs.ATMOS.2013.15","key":"9747_CR14","DOI":"10.4230\/OASIcs.ATMOS.2013.15"},{"issue":"3","key":"9747_CR15","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"1","key":"9747_CR16","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"DB Johnson","year":"1975","unstructured":"Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1), 77\u201384 (1975)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9747_CR17","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9747_CR18","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/net.3230120406","volume":"12","author":"N Katoh","year":"1982","unstructured":"Katoh, N., Ibaraki, T., Mine, H.: An efficient algorithm for k shortest simple paths. Networks 12(4), 411\u2013427 (1982)","journal-title":"Networks"},{"key":"9747_CR19","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1287\/mnsc.18.7.401","volume":"18","author":"EL Lawler","year":"1972","unstructured":"Lawler, E.L.: A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Mgmt. Sci 18, 401\u2013405 (1972)","journal-title":"Mgmt. Sci"},{"doi-asserted-by":"crossref","unstructured":"M\u00fcller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.D.: Timetable information: Models and algorithms. In: ATMOS 2004, pp. 67\u201390 (2004)","key":"9747_CR20","DOI":"10.1007\/978-3-540-74247-0_3"},{"issue":"1","key":"9747_CR21","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1287\/trsc.32.1.54","volume":"32","author":"S Nguyen","year":"1998","unstructured":"Nguyen, S., Pallottino, S., Gendreau, M.: Implicit enumeration of hyperpaths in a logit model for transit networks. Transp. Sci. 32(1), 54\u201364 (1998)","journal-title":"Transp. Sci."},{"doi-asserted-by":"crossref","unstructured":"Rizzi, R., Sacomoto, G., Sagot, M.: Efficiently listing bounded length st-paths. In: IWOCA 2014, pp. 318\u2013329 (2014)","key":"9747_CR22","DOI":"10.1007\/978-3-319-19315-1_28"},{"doi-asserted-by":"crossref","unstructured":"Schulz, F., Wagner, D., Zaroliagis, C.D.: Using multi-level graphs for timetable information in railway systems. In: ALENEX 2002, pp. 43\u201359 (2002)","key":"9747_CR23","DOI":"10.1007\/3-540-45643-0_4"},{"unstructured":"Tulp, E., Siklo\u0307ssy, L.: Trains, an active time-table searcher. In: ECAI 1988, pp. 170\u2013175 (1988)","key":"9747_CR24"},{"doi-asserted-by":"crossref","unstructured":"Vo, K.D., Pham, T.V., Nguyen, H.T., Nguyen, N., Hoai, T.V.: Finding alternative paths in city bus networks. In: IC3INA 2015, pp. 34\u201339 (2015)","key":"9747_CR25","DOI":"10.1109\/IC3INA.2015.7377742"},{"issue":"8","key":"9747_CR26","doi-asserted-by":"crossref","first-page":"1812","DOI":"10.1016\/j.cor.2010.02.005","volume":"39","author":"W Xu","year":"2012","unstructured":"Xu, W., He, S., Song, R., Chaudhry, S.S.: Finding the K shortest paths in a schedule-based transit network. Comput. OR 39(8), 1812\u20131826 (2012)","journal-title":"Comput. OR"},{"key":"9747_CR27","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"JY Yen","year":"1971","unstructured":"Yen, J.Y.: Finding the k shortest loopless paths in a network. Mgmt. Sci. 17, 712\u2013716 (1971)","journal-title":"Mgmt. Sci."},{"unstructured":"Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. In: INFOCOM 2005, pp. 2658\u20132669 (2005)","key":"9747_CR28"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9747-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9747-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9747-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T07:09:14Z","timestamp":1568704154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9747-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,11]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9747"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9747-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,1,11]]}}}