{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T19:30:00Z","timestamp":1760470200894,"version":"3.40.3"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319388502"},{"type":"electronic","value":"9783319388519"}],"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-38851-9_2","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T11:33:54Z","timestamp":1464694434000},"page":"17-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast Exact Computation of Isochrones in Road Networks"],"prefix":"10.1007","author":[{"given":"Moritz","family":"Baum","sequence":"first","affiliation":[]},{"given":"Valentin","family":"Buchhold","sequence":"additional","affiliation":[]},{"given":"Julian","family":"Dibbelt","sequence":"additional","affiliation":[]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: HLDB: location-based services in databases. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 339\u2013348. ACM Press, New York (2012)","DOI":"10.1145\/2424321.2424365"},{"key":"2_CR2","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. Technical report abs\/1504.05140, ArXiv e-prints (2015)","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Bauer, V., Gamper, J., Loperfido, R., Profanter, S., Putzer, S., Timko, I.: Computing isochrones in multi-modal, schedule-based transport networks. In: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2008), pp. 78:1\u201378:2. ACM Press, New York (2008)","DOI":"10.1145\/1463434.1463524"},{"key":"2_CR4","unstructured":"Baum, M., Bl\u00e4sius, T., Gemsa, A., Rutter, I., Wegner, F.: Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths. Technical report abs\/1602.01777, ArXiv e-prints (2016)"},{"issue":"7","key":"2_CR5","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1016\/j.jpdc.2012.02.007","volume":"73","author":"D Delling","year":"2013","unstructured":"Delling, D., Goldberg, A.V., Nowatzyk, A., Werneck, R.F.: PHAST: hardware-accelerated shortest path trees. J. Parallel Distrib. Comput. 73(7), 940\u2013952 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-642-20662-7_32","volume-title":"Experimental Algorithms","author":"D Delling","year":"2011","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376\u2013387. Springer, Heidelberg (2011)"},{"key":"2_CR7","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning in road networks. Transportation Science (2015)"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: Proceedings of the 25th International Parallel and Distributed Processing Symposium (IPDPS 2011), pp. 1135\u20131146. IEEE Computer Society (2011)","DOI":"10.1109\/IPDPS.2011.108"},{"key":"2_CR9","unstructured":"Delling, D., Goldberg, A.V., Werneck, R.F.: Faster batched shortest paths inroad networks. In: Proceedings of the 11th Workshop on Algorithmic Approachesfor Transportation Modeling, Optimization, and Systems (ATMOS 2011). OpenAccessSeries in Informatics, vol. 20, pp. 52\u201363. OASIcs (2011)"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Delling, D., Holzer, M., M\u00fcller, K., Schulz, F., Wagner, D.: High-performance multi-level routing. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 73\u201392. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074\/04"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-38527-8_5","volume-title":"Experimental Algorithms","author":"D Delling","year":"2013","unstructured":"Delling, D., Werneck, R.F.: Faster customization of road networks. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 30\u201342. Springer, Heidelberg (2013)"},{"issue":"3","key":"2_CR12","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1109\/TKDE.2014.2345386","volume":"27","author":"D Delling","year":"2015","unstructured":"Delling, D., Werneck, R.F.: Customizable point-of-interest queries in road networks. IEEE Trans. Knowl. Data Eng. 27(3), 686\u2013698 (2015)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74. American Mathematical Society (2009)","DOI":"10.1090\/dimacs\/074"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-319-07959-2_23","volume-title":"Experimental Algorithms","author":"J Dibbelt","year":"2014","unstructured":"Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 271\u2013282. Springer, Heidelberg (2014)"},{"issue":"1","key":"2_CR15","first-page":"108","volume":"21","author":"J Dibbelt","year":"2016","unstructured":"Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. ACM J. Exp. Algorithmics 21(1), 108\u2013122 (2016)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"1","key":"2_CR16","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":"2_CR17","doi-asserted-by":"crossref","unstructured":"Efentakis, A., Grivas, N., Lamprianidis, G., Magenschab, G., Pfoser, D.: Isochrones, traffic and DEMOgraphics. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2013), pp. 548\u2013551. ACM Press, New York (2013)","DOI":"10.1145\/2525314.2525325"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/978-3-662-44777-2_30","volume-title":"Algorithms - ESA 2014","author":"A Efentakis","year":"2014","unstructured":"Efentakis, A., Pfoser, D.: GRASP. Extending graph separators for the single-source shortest-path problem. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 358\u2013370. Springer, Heidelberg (2014)"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-319-20086-6_23","volume-title":"Experimental Algorithms","author":"A Efentakis","year":"2015","unstructured":"Efentakis, A., Pfoser, D., Vassiliou, Y.: SALT. A unified framework for all shortest-path query variants on road networks. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 298\u2013311. Springer, Heidelberg (2015)"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Efentakis, A., Theodorakis, D., Pfoser, D.: Crowdsourcing computing resources for shortest-path computation. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 434\u2013437. ACM Press, New York (2012)","DOI":"10.1145\/2424321.2424383"},{"issue":"3","key":"2_CR21","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L","volume":"36","author":"M Erwig","year":"2000","unstructured":"Erwig, M.: The graph voronoi diagram with applications. Networks 36(3), 156\u2013163 (2000)","journal-title":"Networks"},{"key":"2_CR22","unstructured":"Foti, F., Waddell, P., Luxen, D.: A generalized computational framework for accessibility: from the pedestrian to the metropolitan scale. In: Proceedings of the 4th TRB Conference on Innovations in Travel Modeling. Transportation Research Board (2012)"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Gamper, J., B\u00f6hlen, M., Cometti, W., Innerebner, M.: Defining isochrones in multimodal spatial networks. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM 2011), pp. 2381\u20132384. ACM Press, New York (2011)","DOI":"10.1145\/2063576.2063972"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/978-3-642-31235-9_35","volume-title":"Scientific and Statistical Database Management","author":"J Gamper","year":"2012","unstructured":"Gamper, J., B\u00f6hlen, M., Innerebner, M.: Scalable computation of isochrones with network expiration. In: Ailamaki, A., Bowers, S. (eds.) SSDBM 2012. LNCS, vol. 7338, pp. 526\u2013543. Springer, Heidelberg (2012)"},{"key":"2_CR25","unstructured":"Geisberger, R.: Advanced Route Planning in Transportation Networks. Ph.D. thesis, Karlsruhe Institute of Technology (2011)"},{"key":"2_CR26","unstructured":"Geisberger, R., Luxen, D., Sanders, P., Neubauer, S., Volker, L.: Fast detour computation for ride sharing. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2010). OpenAccess Series in Informatics, vol. 14, pp. 88\u201399. OASIcs (2010)"},{"issue":"3","key":"2_CR27","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/trsc.1110.0401","volume":"46","author":"R Geisberger","year":"2012","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci. 46(3), 388\u2013404 (2012)","journal-title":"Transp. Sci."},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Grubwinkler, S., Brunner, T., Lienkamp, M.: Range prediction for EVs via crowd-sourcing. In: Proceedings of the 10th IEEE International Vehicle Power and Propulsion Conference (VPPC 2014), pp. 1\u20136. IEEE (2014)","DOI":"10.1109\/VPPC.2014.7007121"},{"key":"2_CR29","first-page":"1","volume":"13","author":"M Holzer","year":"2008","unstructured":"Holzer, M., Schulz, F., Wagner, D.: Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exp. Algorithmics 13, 1\u201326 (2008)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"2_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-37087-8_13","volume-title":"Web and Wireless Geographical Information Systems","author":"M Innerebner","year":"2013","unstructured":"Innerebner, M., B\u00f6hlen, M., Gamper, J.: ISOGA: a system for geographical reachability analysis. In: Liang, S.H.L., Wang, X., Claramunt, C. (eds.) W2GIS 2013. LNCS, vol. 7820, pp. 180\u2013189. Springer, Heidelberg (2013)"},{"issue":"5","key":"2_CR31","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","volume":"14","author":"S Jung","year":"2002","unstructured":"Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng. 14(5), 1029\u20131046 (2002)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), pp. 36\u201345. SIAM (2007)","DOI":"10.1137\/1.9781611972870.4"},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-642-15576-5_30","volume-title":"Advances in Databases and Information Systems","author":"S Marciuska","year":"2010","unstructured":"Marciuska, S., Gamper, J.: Determining objects within isochrones in spatial network databases. In: Catania, B., Ivanovi\u0107, M., Thalheim, B. (eds.) ADBIS 2010. LNCS, vol. 6295, pp. 392\u2013405. Springer, Heidelberg (2010)"},{"issue":"9","key":"2_CR34","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1080\/13658810701587891","volume":"22","author":"A Okabe","year":"2008","unstructured":"Okabe, A., Satoh, T., Furuta, T., Suzuki, A., Okano, K.: Generalized network voronoi diagrams: concepts, computational methods, and applications. Int. J. Geogr. Inf. Sci. 22(9), 965\u2013994 (2008)","journal-title":"Int. J. Geogr. Inf. Sci."},{"issue":"1","key":"2_CR35","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1080\/136588100240976","volume":"14","author":"D O\u2019Sullivan","year":"2000","unstructured":"O\u2019Sullivan, D., Morrison, A., Shearer, J.: Using desktop GIS for the investigation of accessibility by public transport: an isochrone approach. Int. J. Geogr. Inf. Sci. 14(1), 85\u2013104 (2000)","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11, 430\u2013452 (1990)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"2_CR37","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 16\u201329. SIAM (2012)","DOI":"10.1137\/1.9781611972924.2"},{"key":"2_CR38","unstructured":"Schulz, C.: High Quality Graph Partitioning. Ph.D. thesis, Karlsruhe Institute of Technology (2013)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T00:48:44Z","timestamp":1558313324000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_2","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":"1 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}