A breadth-first approach to memory-efficient graph search

Recent work shows that the memory requirements of A * and related graph-search algorithms can be reduced substantially by only storing nodes that are on or near the search frontier, using special techniques to prevent node regeneration, and recovering the solution path by a divide-and-conquer technique. When this approach is used to solve graph-search problems with unit edge costs, we have shown that a breadth-first search strat-egy can be more memory-efficient than a best-first strat-egy. We provide an overview of our work using this approach, which we call breadth-first heuristic search.