{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T15:41:43Z","timestamp":1770478903479,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP6-021235-2"],"award-info":[{"award-number":["FP6-021235-2"]}],"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":[[2009,12]]},"abstract":"<jats:p>During recent years, impressive speed-up techniques for Dijkstra's have been developed. Unfortunately, the most advanced techniques use bidirectional search, which makes it hard to use them in scenarios where a backward search is prohibited. Even worse, such scenarios are widely spread (e.g., timetable-information systems or time-dependent networks).<\/jats:p>\n          <jats:p>\n            In this work, we present a\n            <jats:italic>unidirectional<\/jats:italic>\n            speed-up technique, which competes with bidirectional approaches. Moreover, we show how to exploit the advantage of unidirectional routing for fast exact queries in timetable information systems and for fast approximative queries in time-dependent scenarios. By running experiments on several inputs other than road networks, we show that our approach is very robust to the input.\n          <\/jats:p>","DOI":"10.1145\/1498698.1537599","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":39,"title":["SHARC"],"prefix":"10.1145","volume":"14","author":[{"given":"Reinhard","family":"Bauer","sequence":"first","affiliation":[{"name":"Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Daniel","family":"Delling","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09)","author":"Batz V."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08)","author":"Bauer R."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08)","author":"Bauer R."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)","author":"Bauer R."},{"key":"e_1_2_1_5_1","unstructured":"Bauer R. Delling D. and Wagner D. 2007b. Shortest-path indices: Establishing a methodology for shortest-path problems. Tech. rep. 2007-14 ITI Wagner Faculty of Informatics Universit\u00e4t Karlsruhe (TH).  Bauer R. Delling D. and Wagner D. 2007b. Shortest-path indices: Establishing a methodology for shortest-path problems. Tech. rep. 2007-14 ITI Wagner Faculty of Informatics Universit\u00e4t Karlsruhe (TH)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90009-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_28"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_28"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Delling D. Sanders P. Schultes D. and Wagner D. 2009b. Highway hierarchies star. In Shortest Paths: Ninth DIMACS Implementation Challenge C. Demetrescu A. V. Goldberg and D. S. Johnson Eds. American Mathematical Society Providence RI.  Delling D. Sanders P. Schultes D. and Wagner D. 2009b. Highway hierarchies star. In Shortest Paths: Ninth DIMACS Implementation Challenge C. Demetrescu A. V. Goldberg and D. S. Johnson Eds. American Mathematical Society Providence RI.","DOI":"10.1090\/dimacs\/074\/06"},{"key":"e_1_2_1_12_1","unstructured":"Demetrescu C. Goldberg A. V. and Johnson D. S. Eds. 2006. The 9th DIMACS Implementation Challenge - Shortest Paths.  Demetrescu C. Goldberg A. V. and Johnson D. S. Eds. 2006. The 9th DIMACS Implementation Challenge - Shortest Paths."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_14_1","unstructured":"Flinsenberg I. C. 2004. Route planning algorithms for car navigation. Ph.D. thesis Technische Universiteit Eindhoven.  Flinsenberg I. C. 2004. Route planning algorithms for car navigation. Ph.D. thesis Technische Universiteit Eindhoven."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08)","author":"Geisberger R."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06)","author":"Goldberg A. V."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Goldberg A. V."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04)","author":"Gutman R. J.","year":"2004"},{"key":"e_1_2_1_19_1","unstructured":"Hilger M. 2007. Accelerating point-to-point shortest path computations in large scale metworks. M.S. thesis Technische Universit\u00e4t Berlin.  Hilger M. 2007. Accelerating point-to-point shortest path computations in large scale metworks. M.S. thesis Technische Universit\u00e4t Berlin."},{"key":"e_1_2_1_20_1","unstructured":"Hilger M. K\u00f6hler E. M\u00f6hring R. H. and Schilling H. 2006. Fast point-to-point shortest path computations with arc-flags. In Shortest Paths: Ninth DIMACS Implementation Challenge C. Demetrescu A. V. Goldberg and D. S. Johnson Eds. American Mathematical Society Providence RI.  Hilger M. K\u00f6hler E. M\u00f6hring R. H. and Schilling H. 2006. Fast point-to-point shortest path computations with arc-flags. In Shortest Paths: Ninth DIMACS Implementation Challenge C. Demetrescu A. V. Goldberg and D. S. Johnson Eds. American Mathematical Society Providence RI."},{"key":"e_1_2_1_21_1","volume-title":"METIS: Family of multilevel partitioning algorithms.","author":"Karypis G.","year":"2007"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_13"},{"key":"e_1_2_1_24_1","volume-title":"Geoinformation und Mobilit\u00e4t - von der Forschung zur praktischen Anwendung.","author":"Lauther U."},{"key":"e_1_2_1_25_1","volume-title":"Shortest Paths: Ninth DIMACS Implementation Challenge","author":"Lauther U."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_18"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216585"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PAD.2004.18"},{"key":"e_1_2_1_29_1","volume-title":"SCOTCH: Static mapping, graph, mesh and hypergraph partitioning, and parallel and sequential sparse matrix ordering package.","author":"Pellegrini F.","year":"2007"},{"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.1007\/11561071_51"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_71"},{"key":"e_1_2_1_33_1","unstructured":"Schultes D. 2008. Route planning in road networks. Ph.D. thesis Universit\u00e4t Karlsruhe (TH) Fakult\u00e4t f\u00fcr Informatik.  Schultes D. 2008. Route planning in road networks. Ph.D. thesis Universit\u00e4t Karlsruhe (TH) Fakult\u00e4t f\u00fcr Informatik."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Schultes D."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064546.1103378"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1537599","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1537599","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:43Z","timestamp":1750250743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1537599"}},"subtitle":["Fast and robust unidirectional routing"],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":35,"alternative-id":["10.1145\/1498698.1537599"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1537599","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}