Combining breadth-first and depth-first strategies in searching for optimal treewidth

Abstract

Breadth-first search and depth-first search are two basic search strategies upon which numerous search algorithms are built. Given their fundamental differences in ordering node expansions, combining them in the same search algorithm appears challenging. This paper describes a new way to integrate the two strategies in a single search algorithm that combines the complementary strengths of both strategies to achieve significant speedups over either strategy used alone. The optimal treewidth problem is used as a computational example to illustrate the benefit of this approach.