{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:38:10Z","timestamp":1761176290814,"version":"build-2065373602"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643686318","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T00:00:00Z","timestamp":1761004800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,10,21]]},"abstract":"<jats:p>Bidirectional heuristic search potentially decreases search effort in combinatorial search problems amenable to backward search. To date, bidirectional search has been limited to minimization or shortest path problems. This paper extends the notion of bidirectional heuristic search to (constrained) longest-path problems. We present a bidirectional heuristic search algorithm for longest simple path (LSP) in undirected graphs, and prove its correctness. We then suggest several refinements, as well as a generalization to other types of longest path problems, such as Coil-in-a-box (CIB). Empirical evaluation shows that, as with many forms of bidirectional search, sometimes unidirectional search wins, but for a sizable chunk of problem instances, bidirectional search performs better by expanding fewer nodes and achieves a shorter runtime despite the increased overhead per expansion.<\/jats:p>","DOI":"10.3233\/faia251393","type":"book-chapter","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:00:21Z","timestamp":1761127221000},"source":"Crossref","is-referenced-by-count":0,"title":["Bidirectional Heuristic Search in Longest Path Problems"],"prefix":"10.3233","author":[{"given":"Tzur","family":"Shubi","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Israel"}]},{"given":"Solomon Eyal","family":"Shimony","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Israel"}]},{"given":"Ariel","family":"Felner","sequence":"additional","affiliation":[{"name":"Department of Software and Information Systems Engineering, Ben-Gurion University of the Negev, Israel"}]},{"given":"Shahaf S.","family":"Shperberg","sequence":"additional","affiliation":[{"name":"Department of Software and Information Systems Engineering, Ben-Gurion University of the Negev, Israel"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2025"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA251393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:00:21Z","timestamp":1761127221000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA251393"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,21]]},"ISBN":["9781643686318"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia251393","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,21]]}}}