{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T13:34:51Z","timestamp":1742996091397,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319341705"},{"type":"electronic","value":"9783319341712"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-34171-2_8","type":"book-chapter","created":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T02:34:18Z","timestamp":1464575658000},"page":"102-116","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Computing and Listing st-Paths in Public Transportation Networks"],"prefix":"10.1007","author":[{"given":"Kate\u0159ina","family":"B\u00f6hmov\u00e1","sequence":"first","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":[[2016,5,31]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","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. CoRR abs\/1504.05140 (2015)","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"8_CR2","unstructured":"Bezem, G., Leeuwen, J.V.: Enumeration in graphs. Technical report RUU-CS-87-07, Utrecht University (1987)"},{"key":"8_CR3","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)","DOI":"10.1137\/1.9781611973105.134"},{"key":"8_CR4","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":"8_CR5","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":"8_CR6","doi-asserted-by":"publisher","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":"8_CR7","doi-asserted-by":"publisher","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":"8_CR8","doi-asserted-by":"publisher","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."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC 2014, pp. 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"issue":"2","key":"8_CR10","doi-asserted-by":"publisher","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."},{"issue":"3","key":"8_CR11","doi-asserted-by":"publisher","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":"3","key":"8_CR12","doi-asserted-by":"publisher","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":"1","key":"8_CR13","doi-asserted-by":"publisher","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":"4","key":"8_CR14","doi-asserted-by":"publisher","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 \n                    \n                      \n                    \n                    $$k$$\n                   shortest simple paths. Networks 12(4), 411\u2013427 (1982)","journal-title":"Networks"},{"key":"8_CR15","doi-asserted-by":"publisher","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 \n                    \n                      \n                    \n                    $$k$$\n                   best solutions to discrete optimization problems and its application to the shortest path problem. Mgmt. Sci. 18, 401\u2013405 (1972)","journal-title":"Mgmt. Sci."},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-540-74247-0_3","volume-title":"Algorithmic Methods for Railway Optimization","author":"M M\u00fcller-Hannemann","year":"2007","unstructured":"M\u00fcller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.D.: Timetable information: models and algorithms. In: Geraets, F., Kroon, L., et al. (eds.) ATMOS 2004, Part I. LNCS, vol. 4359, pp. 67\u201390. Springer, Heidelberg (2007)"},{"key":"8_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-319-19315-1_28","volume-title":"Combinatorial Algorithms","author":"R Rizzi","year":"2015","unstructured":"Rizzi, R., Sacomoto, G., Sagot, M.-F.: Efficiently listing bounded length st-paths. In: Jan, K., Miller, M., Froncek, D. (eds.) IWOCA 2014. LNCS, vol. 8986, pp. 318\u2013329. Springer, Heidelberg (2015)"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-45643-0_4","volume-title":"Algorithm Engineering and Experiments","author":"F Schulz","year":"2002","unstructured":"Schulz, F., Wagner, D., Zaroliagis, C.D.: Using multi-level graphs for timetable information in railway systems. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 43\u201359. Springer, Heidelberg (2002)"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"JY Yen","year":"1971","unstructured":"Yen, J.Y.: Finding the \n                    \n                      \n                    \n                    $$k$$\n                   shortest loopless paths in a network. Mgmt. Sci. 17, 712\u2013716 (1971)","journal-title":"Mgmt. Sci."},{"key":"8_CR20","unstructured":"Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. In: INFOCOM 2005, pp. 2658\u20132669 (2005)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-34171-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T00:49:12Z","timestamp":1558313352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-34171-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319341705","9783319341712"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-34171-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"31 May 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}