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

Details

Event The First International Symposium on Search Techniques in Artificial Intelligence and Robotics

Authors

Zhou, Rong
Technical Publications
July 13th 2008
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.

Citation

Zhou, R.; Hansen, E. A. Combining breadth-first and depth-first strategies in searching for optimal treewidth . First International Symposium on Search Techniques in Artificial Intelligence and Robotics; 2008 July 13-14; Chicago, IL.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

FIND OUT MORE
Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.

FIND OUT MORE
News

PARC scientists and staffers are active members and contributors to the science and technology communities.

FIND OUT MORE