{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:12:47Z","timestamp":1762272767657,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,11]]},"DOI":"10.1007\/s10589-021-00303-5","type":"journal-article","created":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T09:03:48Z","timestamp":1626339828000},"page":"377-409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Two new bidirectional search algorithms"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5662-4117","authenticated-orcid":false,"given":"John A.","family":"Pavlik","sequence":"first","affiliation":[]},{"given":"Edward C.","family":"Sewell","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9042-8750","authenticated-orcid":false,"given":"Sheldon H.","family":"Jacobson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"issue":"03","key":"303_CR1","first-page":"2327","volume":"34","author":"V Alc\u00e1zar","year":"2020","unstructured":"Alc\u00e1zar, V., Riddle, P., Barley, M.: A unifying view on individual bounds and heuristic inaccuracies in bidirectional search. Proc. AAAI Conf. Artif. Intell. 34(03), 2327\u20132334 (2020)","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"303_CR2","doi-asserted-by":"crossref","unstructured":"Barker, J.K., Korf, R.E.: Limitations of front-to-end bidirectional heuristic search. In: Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)","DOI":"10.1609\/aaai.v29i1.9374"},{"key":"303_CR3","unstructured":"Barley, M., Riddle, P., Lopez, C.L., Dobson, S., Pohl, I.S.: GBFHS: A generalized breadth-first heuristic search algorithm. In: Eleventh Annual Symposium on Combinatorial Search (2018)"},{"issue":"1","key":"303_CR4","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/322358.322360","volume":"30","author":"D de Champeaux","year":"1983","unstructured":"de Champeaux, D.: Bidirectional heuristic search again. J. ACM 30(1), 22\u201332 (1983)","journal-title":"J. ACM"},{"key":"303_CR5","doi-asserted-by":"crossref","unstructured":"Chen, J., Holte, R.C., Zilles, S., Sturtevant, N.R.: Front-to-end bidirectional heuristic search with near-optimal node expansions. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, pp. 489\u2013495 (2017)","DOI":"10.24963\/ijcai.2017\/69"},{"key":"303_CR6","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179","volume-title":"Linear Programming and Extensions","author":"G Dantzig","year":"1963","unstructured":"Dantzig, G.: Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963)"},{"key":"303_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W., et al.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"10","key":"303_CR8","first-page":"1009","volume":"82","author":"H Dweighter","year":"1975","unstructured":"Dweighter, H.: Elementary problem: E2569. Am. Math. Mon 82(10), 1009\u20131010 (1975)","journal-title":"Am. Math. Mon"},{"key":"303_CR9","doi-asserted-by":"crossref","unstructured":"Eckerle, J., Chen, J., Sturtevant, N.R., Zilles, S., Holte, R.C.: Sufficient conditions for node expansion in bidirectional heuristic search. In: Twenty-Seventh International Conference on Automated Planning and Scheduling (2017)","DOI":"10.1609\/icaps.v27i1.13825"},{"issue":"1","key":"303_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.5121\/acij.2012.3109","volume":"3","author":"J Ghorpade","year":"2012","unstructured":"Ghorpade, J., Parande, J., Kulkarni, M., Bawaskar, A.: GPGPU processing in CUDA architecture. Adv. Comput. Int. J. 3(1), 105\u2013120 (2012)","journal-title":"Adv. Comput. Int. J."},{"issue":"2","key":"303_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P Hart","year":"1968","unstructured":"Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"303_CR12","doi-asserted-by":"crossref","unstructured":"Helmert, M.: Landmark heuristics for the pancake problem. In: Third Annual Symposium on Combinatorial Search (2010)","DOI":"10.1609\/socs.v1i1.18176"},{"key":"303_CR13","doi-asserted-by":"crossref","unstructured":"Holte, R.C., Felner, A., Sharon, G., Sturtevant, N.R.: Bidirectional search that is guaranteed to meet in the middle. In: Thirtieth AAAI Conference on Artificial Intelligence (2016)","DOI":"10.1016\/j.artint.2017.05.004"},{"key":"303_CR14","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.artint.2017.05.004","volume":"252","author":"RC Holte","year":"2017","unstructured":"Holte, R.C., Felner, A., Sharon, G., Sturtevant, N.R., Chen, J.: MM: a bidirectional search algorithm that is guaranteed to meet in the middle. Artif. Intell. 252, 232\u2013266 (2017)","journal-title":"Artif. Intell."},{"key":"303_CR15","unstructured":"Intel: Intel 64 and IA-32 Architectures Software Developer\u2019s Manual Combined Volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4 (2020). https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/download\/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4.html. Accessed 19 Jan 2021"},{"key":"303_CR16","doi-asserted-by":"crossref","unstructured":"Jiang, J., Huang, H., Liao, J., Chen, S.: Extending Dijkstra\u2019s shortest path algorithm for software defined networking. In: The 16th Asia-Pacific Network Operations and Management Symposium, pp. 1\u20134 (2014)","DOI":"10.1109\/APNOMS.2014.6996609"},{"key":"303_CR17","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1613\/jair.460","volume":"7","author":"H Kaindl","year":"1997","unstructured":"Kaindl, H., Kainz, G.: Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. 7, 283\u2013317 (1997)","journal-title":"J. Artif. Intell. Res."},{"issue":"3","key":"303_CR18","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1093\/comjnl\/9.3.275","volume":"9","author":"TAJ Nicholson","year":"1966","unstructured":"Nicholson, T.A.J.: Finding the shortest route between two points in a network. Comput. J. 9(3), 275\u2013280 (1966)","journal-title":"Comput. J."},{"key":"303_CR19","unstructured":"NVIDIA: CUDA math api (2019). https:\/\/docs.nvidia.com\/cuda\/pdf\/CUDA_Math_API.pdf. Accessed 19 Jan 2021"},{"key":"303_CR20","unstructured":"NVIDIA: Cuda c++ programming guide (2021). https:\/\/docs.nvidia.com\/cuda\/pdf\/CUDA_C_Programming_Guide.pdf. Accessed 20 Jan 2021"},{"key":"303_CR21","doi-asserted-by":"crossref","unstructured":"Peyer, S., Rautenbach, D., Vygen, J.: A generalization of Dijkstra\u2019s shortest path algorithm with applications to VLSI routing. J Discrete Algorithms 7(4), 377\u2013390 (2009)","DOI":"10.1016\/j.jda.2007.08.003"},{"key":"303_CR22","doi-asserted-by":"crossref","unstructured":"Pohl, I.S.: Bi-directional and heuristic search in path problems. PhD Thesis, Stanford University, Stanford, CA, USA (1969)","DOI":"10.2172\/4785039"},{"key":"303_CR23","first-page":"127","volume":"6","author":"IS Pohl","year":"1971","unstructured":"Pohl, I.S.: Bi-directional search. Mach. Intell. 6, 127\u2013140 (1971)","journal-title":"Mach. Intell."},{"key":"303_CR24","volume-title":"Artificial Intelligence: A Modern Approach","author":"S Russell","year":"2009","unstructured":"Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Prentice Hall Press, Upper Saddle River (2009)","edition":"3"},{"key":"303_CR25","unstructured":"Sadhukhan, S.K.: A new approach to bidirectional heuristic search using error functions. In: Proceedings of 1st International Conference on Intelligent Infrastructure at the 47th Annual National Convention Computer Soceity of India (CSI-2012) (2012)"},{"key":"303_CR26","doi-asserted-by":"publisher","first-page":"103405","DOI":"10.1016\/j.artint.2020.103405","volume":"291","author":"EC Sewell","year":"2021","unstructured":"Sewell, E.C., Jacobson, S.H.: Dynamically improved bounds bidirectional search. Artif. Intell. 291, 103405 (2021)","journal-title":"Artif. Intell."},{"key":"303_CR27","doi-asserted-by":"crossref","unstructured":"Shperberg, S.S., Felner, A., Sturtevant, N.R., Hayoun, A., Shimony, S.E.: Enriching non-parametric bidirectional search algorithms. In: AAAI Conference on Artificial Intelligence, vol.\u00a033 (2019)","DOI":"10.1609\/aaai.v33i01.33012379"},{"issue":"2","key":"303_CR28","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/322003.322004","volume":"24","author":"L Sint","year":"1977","unstructured":"Sint, L., de Champeaux, D.: An improved bidirectional heuristic search algorithm. J. ACM 24(2), 177\u2013191 (1977)","journal-title":"J. ACM"},{"key":"303_CR29","unstructured":"Zahavi, U., Felner, A., Schaeffer, J., Sturtevant, N.: Inconsistent heuristics. In: Proceedings of the 22nd national conference on Artificial intelligence\u2014Volume 2, AAAI\u201907, pp. 1211\u20131216. AAAI Press, Vancouver, British Columbia, Canada (2007)"},{"issue":"4","key":"303_CR30","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1080\/13658810801949850","volume":"23","author":"W Zeng","year":"2009","unstructured":"Zeng, W., Church, R.L.: Finding shortest paths on real road networks: the case for A*. Int. J. Geograph. Inf. Sci. 23(4), 531\u2013543 (2009)","journal-title":"Int. J. Geograph. Inf. Sci."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00303-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00303-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00303-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T10:11:22Z","timestamp":1672827082000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00303-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["303"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00303-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"25 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}