@inproceedings{0317ae3725604400a2433140fa82bfca,
title = "An improved meet in the middle algorithm for graphs with unit costs",
abstract = "This paper proves several new properties of the Meet in the Middle (MMe) bidirectional heuristic search algorithm when applied to graphs with unit edge costs. Primarily, it is shown that the length of the first path discovered by MMe never exceeds the optimal length by more than one and that if the length of the first path found is odd, then it must be optimal. These properties suggest that the search strategy should emphasize finding a complete path as soon as possible. Computational experiments demonstrate that fully exploiting these new properties can decrease the number of nodes expanded by anywhere from twofold to over tenfold.",
author = "Sewell, {Edward C.} and Pavlik, {John A.} and Jacobson, {Sheldon H.}",
note = "Publisher Copyright: Copyright {\textcopyright} 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 12th International Symposium on Combinatorial Search, SoCS 2019 ; Conference date: 16-07-2019 Through 17-07-2019",
year = "2019",
language = "English (US)",
series = "Proceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019",
publisher = "American Association for Artificial Intelligence (AAAI) Press",
pages = "145--149",
editor = "Pavel Surynek and William Yeoh",
booktitle = "Proceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019",
address = "United States",
}