{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:57:54Z","timestamp":1766066274550,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WA 654\/16-1"],"award-info":[{"award-number":["WA 654\/16-1"]}],"id":[{"id":"10.13039\/501100001659","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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            Exploiting parallelism in route planning algorithms is a challenging algorithmic problem with obvious applications in mobile navigation and timetable information systems. In this work, we present a novel algorithm for the one-to-all\n            <jats:italic>profile-search<\/jats:italic>\n            problem in public transportation networks. It answers the question for all fastest connections between a given station &lt;it&gt;S&lt;\/it&gt; and any other station at any time of the day in a single query. This algorithm allows for a very natural parallelization, yielding excellent speed-ups on standard multicore servers. Our approach exploits the facts that, first, time-dependent travel-time functions in such networks can be represented as a special class of piecewise linear functions and, second, only few connections from &lt;it&gt;S&lt;\/it&gt; are useful to travel far away. Introducing the\n            <jats:italic>connection-setting<\/jats:italic>\n            property, we are able to extend Dijkstra's algorithm in a sound manner. Furthermore, we also accelerate station-to-station queries by preprocessing important connections within the public transportation network. As a result, we are able to compute all relevant connections between two random stations in a complete public transportation network of a big city (New York) on a standard multi-core server in real time.\n          <\/jats:p>","DOI":"10.1145\/2133803.2345678","type":"journal-article","created":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T12:50:57Z","timestamp":1350391857000},"source":"Crossref","is-referenced-by-count":17,"title":["Parallel computation of best connections in public transportation networks"],"prefix":"10.1145","volume":"17","author":[{"given":"Daniel","family":"Delling","sequence":"first","affiliation":[{"name":"Microsoft Research Silicon Valley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bastian","family":"Katz","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Pajor","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,10,16]]},"reference":[{"volume":"6630","volume-title":"Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)","author":"Abraham I.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01408019"},{"volume":"5868","volume-title":"Robust and Online Large-Scale Optimization. Lecture Notes in Computer Science Series","author":"Ahuja R. K.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03456-5_24"},{"volume":"6346","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms (ESA'10)","author":"Bast H.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1537599"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20382"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/358690.358717"},{"key":"e_1_2_1_9_1","unstructured":"Dean B. C. 1999. Continuous-time dynamic shortest path algorithms. M.S. thesis Massachusetts Institute of Technology.  Dean B. C. 1999. Continuous-time dynamic shortest path algorithms. M.S. thesis Massachusetts Institute of Technology."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9341-0"},{"volume-title":"PHAST: Hardware-accelerated shortest path trees. J. Parallel Distrib. Comput.","year":"2012","author":"Delling D.","key":"e_1_2_1_11_1"},{"volume-title":"Proceeding of the 24th International Parallel and Distributed Processing Symposium (IPDPS'10)","author":"Delling D.","key":"e_1_2_1_12_1"},{"volume":"5757","volume-title":"Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09)","author":"Delling D.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05465-5_7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05465-5_8"},{"volume":"5038","volume-title":"Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08)","author":"Disser Y.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Geisberger R. Sanders P. Schultes D. and \n      \n      \n      Delling D\n      \n  \n  . \n  2008\n  . Contraction hierarchies: faster and simpler hierarchical routing in road networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08) Lecture Notes in Computer Science vol. \n  5038 Springer Berlin. 319--333.   Geisberger R. Sanders P. Schultes D. and Delling D. 2008. Contraction hierarchies: faster and simpler hierarchical routing in road networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08) Lecture Notes in Computer Science vol. 5038 Springer Berlin. 319--333.","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00105-3"},{"volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 281--297","year":"1967","author":"MacQueen J.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07)","author":"Madduri K.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08)","volume":"5038","author":"McGeoch C. C., Ed.","year":"2008"},{"volume":"1461","volume-title":"Proceedings of the 6th Annual European Symposium on Algorithms (ESA'98)","author":"Meyer U.","key":"e_1_2_1_25_1"},{"volume":"4359","volume-title":"Algorithmic Methods for Railway Optimization. Lecture Notes in Computer Science","author":"M\u00fcller","key":"e_1_2_1_26_1"},{"volume-title":"Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)","author":"M\u00fcller","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214078"},{"volume-title":"Proceedings of the International Conference on Parallel Processing. IEEE, 14--20","author":"Paige R. C.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1227166"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90017-7"},{"volume":"1668","volume-title":"Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE'99)","author":"Schulz F.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00025-J"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2345678","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133803.2345678","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:05:52Z","timestamp":1750241152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2345678"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":33,"alternative-id":["10.1145\/2133803.2345678"],"URL":"https:\/\/doi.org\/10.1145\/2133803.2345678","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}