{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:14Z","timestamp":1750220054125,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            We study exact, efficient, and practical algorithms for route planning applications in large road networks. On the one hand, such algorithms should be able to answer shortest path queries within milliseconds. On the other hand, routing applications often require integrating the current traffic situation, planning ahead with predictions for future traffic, respecting forbidden turns, and many other features depending on the specific application. Therefore, such algorithms must be flexible and able to support a variety of problem variants. In this work, we revisit the A* algorithm to build a simple, extensible, and unified algorithmic framework applicable to many route planning problems. A* has been previously used for routing in road networks. However, its performance was not competitive because no sufficiently fast and tight distance estimation function was available. We present a novel, efficient, and accurate A* heuristic using Contraction Hierarchies, another popular speedup technique. The core of our heuristic is a new Contraction Hierarchies query algorithm called\n            <jats:italic>Lazy RPHAST<\/jats:italic>\n            , which can efficiently compute shortest distances from many incrementally provided sources toward a common target. Additionally, we describe A* optimizations to accelerate the processing of low-degree vertices, which are typical in road networks, and present a new pruning criterion for symmetrical bidirectional A*. An extensive experimental study confirms the practicality of our approach for many applications.\n          <\/jats:p>","DOI":"10.1145\/3571282","type":"journal-article","created":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T13:06:49Z","timestamp":1669813609000},"page":"1-28","source":"Crossref","is-referenced-by-count":0,"title":["Using Incremental Many-to-One Queries to Build a Fast and Tight Heuristic for A* in Road Networks"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3391-6221","authenticated-orcid":false,"given":"Ben","family":"Strasser","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4746-3582","authenticated-orcid":false,"given":"Tim","family":"Zeitz","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,3]]},"reference":[{"issue":"1","key":"e_1_3_2_2_2","first-page":"1","article-title":"Alternative routes in road networks","volume":"18","author":"Abraham Ittai","year":"2013","unstructured":"Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2013. Alternative routes in road networks. ACM Journal of Experimental Algorithmics 18, 1 (2013), 1\u201317.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","unstructured":"Roland Bader Jonathan Dees Robert Geisberger and Peter Sanders. 2011. Alternative route graphs in road networks. In Theory and Practice of Algorithms in (Computer) Systems . Lecture Notes in Computer Science Vol. 6595. Springer 21\u201332.","DOI":"10.1007\/978-3-642-19754-3_5"},{"key":"e_1_3_2_5_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","volume-title":"Algorithm Engineering\u2014Selected Results and Surveys","author":"Bast Hannah","year":"2016","unstructured":"Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias M\u00fcller\u2013Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2016. Route planning in transportation networks. In Algorithm Engineering\u2014Selected Results and Surveys. Lecture Notes in Computer Science, Vol. 9220. Springer, 19\u201380."},{"key":"e_1_3_2_6_2","volume-title":"Time-Dependent Route Planning with Contraction Hierarchies","author":"Batz Gernot Veit","year":"2014","unstructured":"Gernot Veit Batz. 2014. Time-Dependent Route Planning with Contraction Hierarchies. Ph.D. dissertation. Karlsruhe Institute of Technology (KIT)."},{"key":"e_1_3_2_7_2","first-page":"97","volume-title":"Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX \u201909)","author":"Batz Gernot Veit","year":"2009","unstructured":"Gernot Veit Batz, Daniel Delling, Peter Sanders, and Christian Vetter. 2009. Time-dependent contraction hierarchies. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX \u201909). 97\u2013105."},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","unstructured":"Gernot Veit Batz Robert Geisberger Sabine Neubauer and Peter Sanders. 2010. Time-dependent contraction hierarchies and approximation. In Experimental Algorithms . Lecture Notes in Computer Science Vol. 6049. Springer 166\u2013177. http:\/\/www.springerlink.com\/content\/u787292691813526\/.","DOI":"10.1007\/978-3-642-13193-6_15"},{"issue":"1","key":"e_1_3_2_9_2","first-page":"1","article-title":"Minimum time-dependent travel times with contraction hierarchies","volume":"18","author":"Batz Gernot Veit","year":"2013","unstructured":"Gernot Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. 2013. Minimum time-dependent travel times with contraction hierarchies. ACM Journal of Experimental Algorithmics 18, 1.4 (April2013), 1\u201343.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.tcs.2016.07.003","article-title":"Search-space size in contraction hierarchies","volume":"645","author":"Bauer Reinhard","year":"2016","unstructured":"Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. 2016. Search-space size in contraction hierarchies. Theoretical Computer Science 645 (2016), 112\u2013127.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"e_1_3_2_11_2","first-page":"1","article-title":"Combining hierarchical and goal-directed speed-up techniques for Dijkstra\u2019s algorithm","volume":"15","author":"Bauer Reinhard","year":"2010","unstructured":"Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. 2010. Combining hierarchical and goal-directed speed-up techniques for Dijkstra\u2019s algorithm. ACM Journal of Experimental Algorithmics 15, 2.3 (Jan. 2010), 1\u201331.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5445\/IR\/1000082225"},{"key":"e_1_3_2_13_2","article-title":"Shortest feasible paths with charging stops for battery electric vehicles","author":"Baum Moritz","year":"2019","unstructured":"Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Z\u00fcndorf. 2019. Shortest feasible paths with charging stops for battery electric vehicles. Transportation Science 53, 6 (2019), 1501\u20131799.","journal-title":"Transportation Science"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00655-9"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Moritz Baum Julian Dibbelt Thomas Pajor and Dorothea Wagner. 2016. Dynamic time-dependent route planning in road networks with user preferences. In Experimental Algorithms . Lecture Notes in Computer Science Vol. 9685. Springer 33\u201349.","DOI":"10.1007\/978-3-319-38851-9_3"},{"key":"e_1_3_2_16_2","first-page":"1199","volume-title":"Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI \u201919)","author":"Bono Massimo","year":"2019","unstructured":"Massimo Bono, Alfonso Emilio Gerevini, Daniel Damir Harabor, and Peter J. Stuckey. 2019. Path planning with CPD heuristics. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI \u201919). 1199\u20131205. DOI:10.24963\/ijcai.2019\/167"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3362693"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SEA.2021.18"},{"key":"e_1_3_2_19_2","volume-title":"Proceedings of the 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS\u201920) (OpenAccess Series in Informatics (OASIcs))","author":"Buchhold Valentin","year":"2020","unstructured":"Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Z\u00fcndorf. 2020. Customizable contraction hierarchies with turn costs. In Proceedings of the 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS\u201920) (OpenAccess Series in Informatics (OASIcs)), Dennis Huisman and Christos Zaroliagis (Eds.). Accepted for publication."},{"key":"e_1_3_2_20_2","first-page":"1427","volume-title":"Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI \u201918)","author":"Cohen Liron","year":"2018","unstructured":"Liron Cohen, Tansel Uras, Shiva Jahangiri, Aliyah Arunasalam, Sven Koenig, and T. K. Satish Kumar. 2018. The FastMap algorithm for shortest path computations. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI \u201918). 1427\u20131433. DOI:10.24963\/ijcai.2018\/198"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5445\/IR\/1000011046"},{"issue":"7","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"940","DOI":"10.1016\/j.jpdc.2012.02.007","article-title":"PHAST: Hardware-accelerated shortest path trees","volume":"73","author":"Delling Daniel","year":"2013","unstructured":"Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2013. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing 73, 7 (2013), 940\u2013952.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"2","key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1287\/trsc.2014.0579","article-title":"Customizable route planning in road networks","volume":"51","author":"Delling Daniel","year":"2017","unstructured":"Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2017. Customizable route planning in road networks. Transportation Science 51, 2 (2017), 566\u2013591.","journal-title":"Transportation Science"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.ATMOS.2011.52"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_4"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1110.0448"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00172"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","unstructured":"Daniel Delling and Dorothea Wagner. 2007. Landmark-based routing in dynamic graphs. In Experimental Algorithms . Lecture Notes in Computer Science Vol. 4525. Springer 52\u201365.","DOI":"10.1007\/978-3-540-72845-0_5"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/074"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"Julian Dibbelt Ben Strasser and Dorothea Wagner. 2015. Fast exact shortest path and distance queries on road networks with parametrized costs. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems . ACM New York NY Article 66 4 pages. DOI:10.1145\/2820783.2820856","DOI":"10.1145\/2820783.2820856"},{"issue":"1","key":"e_1_3_2_31_2","first-page":"Article 1.5, 49","article-title":"Customizable contraction hierarchies","volume":"21","author":"Dibbelt Julian","year":"2016","unstructured":"Julian Dibbelt, Ben Strasser, and Dorothea Wagner. 2016. Customizable contraction hierarchies. ACM Journal of Experimental Algorithmics 21, 1 (April2016), Article 1.5, 49 pages.","journal-title":"ACM Journal of Experimental Algorithmics"},{"issue":"1","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra Edsger W.","year":"1959","unstructured":"Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1 (1959), 269\u2013271.","journal-title":"Numerische Mathematik"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_3_2_34_2","volume-title":"Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI \u201911)","author":"Eisner Jochen","year":"2011","unstructured":"Jochen Eisner, Stefan Funke, and Sabine Storandt. 2011. Optimal route planning for electric vehicles in large networks. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI \u201911)."},{"key":"e_1_3_2_35_2","first-page":"893","volume-title":"Proceedings of the 40th International Conference on Very Large Databases (VLDB \u201914)","author":"Funke Stefan","year":"2014","unstructured":"Stefan Funke, Andr\u00e9 Nusser, and Sabine Storandt. 2014. On k-path covers and their applications. In Proceedings of the 40th International Conference on Very Large Databases (VLDB \u201914). 893\u2013902."},{"key":"e_1_3_2_36_2","first-page":"124","volume-title":"Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX \u201910)","author":"Geisberger Robert","year":"2010","unstructured":"Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. 2010. Route planning with flexible objective functions. In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX \u201910). 124\u2013137."},{"issue":"3","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/trsc.1110.0401","article-title":"Exact routing in large road networks using contraction hierarchies","volume":"46","author":"Geisberger Robert","year":"2012","unstructured":"Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science 46, 3 (Aug. 2012), 388\u2013404.","journal-title":"Transportation Science"},{"key":"e_1_3_2_38_2","doi-asserted-by":"crossref","unstructured":"Robert Geisberger and Christian Vetter. 2011. Efficient routing in road networks with turn costs. In Experimental Algorithms . Lecture Notes in Computer Science Vol. 6630. Springer 100\u2013111.","DOI":"10.1007\/978-3-642-20662-7_9"},{"key":"e_1_3_2_39_2","first-page":"156","volume-title":"Proceedings of the 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA \u201905)","author":"Goldberg Andrew V.","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA \u201905). 156\u2013165."},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"Andrew V. Goldberg Haim Kaplan and Renato F. Werneck. 2007. Better landmarks within reach. In Experimental Algorithms . Lecture Notes in Computer Science Vol. 4525. Springer 38\u201351.","DOI":"10.1007\/978-3-540-72845-0_4"},{"key":"e_1_3_2_41_2","first-page":"26","volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX \u201905)","author":"Goldberg Andrew V.","year":"2005","unstructured":"Andrew V. Goldberg and Renato F. Werneck. 2005. Computing point-to-point shortest paths from external memory. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX \u201905). 26\u201340."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.3390\/a12090196"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3173045"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart Peter E.","year":"1968","unstructured":"Peter E. Hart, Nils Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4 (1968), 100\u2013107.","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","unstructured":"Tim Kieritz Dennis Luxen Peter Sanders and Christian Vetter. 2010. Distributed time-dependent contraction hierarchies. In Experimental Algorithms . Lecture Notes in Computer Science Vol. 6049. Springer 83\u201393.","DOI":"10.1007\/978-3-642-13193-6_8"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SEA.2020.17"},{"key":"e_1_3_2_47_2","volume-title":"Alternative Route Techniques and Their Applications to the Stochastics On-Time Arrival Problem","author":"Kobitzsch Moritz Helge","year":"2015","unstructured":"Moritz Helge Kobitzsch. 2015. Alternative Route Techniques and Their Applications to the Stochastics On-Time Arrival Problem. Ph.D. dissertation. Karlsruhe Institute of Technology (KIT)."},{"key":"e_1_3_2_48_2","first-page":"767","volume-title":"Advances in Neural Information Processing Systems 16 (Neural Information Processing Systems, NIPS 2003, December 8\u201313, 2003, Vancouver and Whistler, British Columbia, Canada)","author":"Likhachev Maxim","year":"2003","unstructured":"Maxim Likhachev, Geoffrey J. Gordon, and Sebastian Thrun. 2003. ARA*: Anytime A* with provable bounds on sub-optimality. In Advances in Neural Information Processing Systems 16 (Neural Information Processing Systems, NIPS 2003, December 8\u201313, 2003, Vancouver and Whistler, British Columbia, Canada), Sebastian Thrun, Lawrence K. Saul, and Bernhard Sch\u00f6lkopf (Eds.). MIT Press, Cambridge, MA, 767\u2013774."},{"key":"e_1_3_2_49_2","unstructured":"Microsoft Bing Blogs. Bing Maps New Routing Engine. Retrieved January 25 2020 from https:\/\/blogs.bing.com\/maps\/2012\/01\/05\/bing-maps-new-routing-engine\/"},{"key":"e_1_3_2_50_2","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1002\/net.20438","article-title":"Bidirectional A* search on time-dependent road networks","volume":"59","author":"Nannicini Giacomo","year":"2012","unstructured":"Giacomo Nannicini, Daniel Delling, Leo Liberti, and Dominik Schultes. 2012. Bidirectional A* search on time-dependent road networks. Networks 59 (2012), 240\u2013251.","journal-title":"Networks"},{"key":"e_1_3_2_51_2","volume-title":"Traveling Without Waiting in Time-Dependent Networks Is NP-hard","author":"Orda Ariel","year":"1989","unstructured":"Ariel Orda and Raphael Rom. 1989. Traveling Without Waiting in Time-Dependent Networks Is NP-hard. Technical Report. Department of Electrical Engineering, Technion-Israel Institute of Technology."},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","unstructured":"Frank Schulz Dorothea Wagner and Christos Zaroliagis. 2002. Using multi-level graphs for timetable information in railway systems. In Algorithm Engineering and Experiments . Lecture Notes in Computer Science Vol. 2409. Springer 43\u201359.","DOI":"10.1007\/3-540-45643-0_4"},{"key":"e_1_3_2_53_2","unstructured":"Ben Strasser Daniel Harabor and Adi Botea. 2014. Fast first-move queries through run-length encoding. In Proceedings of the 7th Annual Symposium on Combinatorial Search (SOCS \u201914) ."},{"issue":"3","key":"e_1_3_2_54_2","article-title":"Space-efficient, fast and exact routing in time-dependent road networks","volume":"14","author":"Strasser Ben","year":"2021","unstructured":"Ben Strasser, Dorothea Wagner, and Tim Zeitz. 2021. Space-efficient, fast and exact routing in time-dependent road networks. Algorithms 14, 3 (Jan. 2021), 90. https:\/\/www.mdpi.com\/1999-4893\/14\/3\/90.","journal-title":"Algorithms"},{"key":"e_1_3_2_55_2","first-page":"Article 6, 16 p","volume-title":"Proceedings of the 19th International Symposium on Experimental Algorithms (SEA\u201921) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"190","author":"Strasser Ben","year":"2021","unstructured":"Ben Strasser and Tim Zeitz. 2021. A fast and tight heuristic for A* in road networks. In Proceedings of the 19th International Symposium on Experimental Algorithms (SEA\u201921) (Leibniz International Proceedings in Informatics (LIPIcs)), David Coudert and Emanuele Natale (Eds.), Vol. 190. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 6, 16 pages. DOI:10.4230\/LIPIcs.SEA.2021.6"},{"key":"e_1_3_2_56_2","first-page":"241","volume-title":"Proceedings of the 8th Annual Symposium on Combinatorial Search (SOCS \u201915)","author":"Sturtevant Nathan R.","year":"2015","unstructured":"Nathan R. Sturtevant, Jason M. Traish, James R. Tulip, Tansel Uras, Sven Koenig, Ben Strasser, Adi Botea, Daniel Harabor, and Steve Rabin. 2015. The grid-based path planning competition: 2014 entries and results. In Proceedings of the 8th Annual Symposium on Combinatorial Search (SOCS \u201915). 241."},{"key":"e_1_3_2_57_2","doi-asserted-by":"crossref","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","author":"Tarjan Robert","year":"1972","unstructured":"Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1, 2 (1972), 146\u2013160.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","unstructured":"Tansel Uras and Sven Koenig. 2014. Identifying hierarchies for fast optimal search. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI \u201914) . 878\u2013884.","DOI":"10.1609\/aaai.v28i1.8845"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2022.106287"},{"key":"e_1_3_2_60_2","first-page":"975","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence and the 14th Conference on Innovative Applications of Artificial Intelligence","author":"Zhou Rong","year":"2002","unstructured":"Rong Zhou and Eric A. Hansen. 2002. Multiple sequence alignment using anytime A*. In Proceedings of the 18th National Conference on Artificial Intelligence and the 14th Conference on Innovative Applications of Artificial Intelligence. 975\u2013977."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571282","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:22Z","timestamp":1750183702000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":59,"alternative-id":["10.1145\/3571282"],"URL":"https:\/\/doi.org\/10.1145\/3571282","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,12,31]]}}}