12-10-2010, 10:58 AM
[attachment=5645]
Combining Breadth-First and Depth-First Strategies in Searching for Treewidth
Rong Zhou
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, CA 94304
Eric A. Hansen
Dept. of Computer Science and Engineering
Mississippi State University
Mississippi State, MS 39762
Abstract Breadth-first and depth-first search are basic search strategies upon which many other search algorithms are built. In this paper, we describe an approach to integrating these two strategies in a single algorithm that combines the complementary strengths of both. We show the benefits of this approach using the tree width problem as an example. 1 Introduction Breadth-first and depth-first search are basic search strategies upon which many other search algorithms are built. Given the very different way in which they order node expansions, it is not obvious that they can be combined in the same search algorithm. In this paper, we describe an approach to integrating these two strategies in a single algorithm that combines the complementary strengths of both. To illustrate the benefits of this approach, we use the treewidth problem as an example. The treewidth of a graph (also known as the induced treewidth) is a measure of how similar the graph is to a tree, which has a treewidth of 1. A completely connected graph is least similar to a tree, and has a treewidth of n − 1, where n is the number of vertices in the graph. Most graphs have a treewidth that is somewhere in between 1 and n − 1. There is a close relationship between treewidth and vertex elimination orders. Eliminating a vertex of a graph is defined as follows: an edge is added to every pair of neighbors of the vertex that are not adjacent, and all the edges incident to the vertex are removed along with the vertex itself. A vertex elimination order specifies an order in which to eliminate all the vertices of a graph, one after another. For each elimination order, the maximum degree (i.e., the number of neighbors) of any vertex when it is eliminated from the graph is defined as the width of the elimination order. The treewidth of a graph is defined as the minimum width over all possible elimination orders, and an optimal elimination order is any order whose width is the same as the treewidth.