Combining BreadthFirst and DepthFirst Strategies in Searching for Treewidth
project report helper Active In SP Posts: 2,270 Joined: Sep 2010 
12102010, 10:58 AM
dfs and bfs.pdf (Size: 501.4 KB / Downloads: 73) Combining BreadthFirst and DepthFirst 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 Breadthfirst and depthfirst 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 Breadthfirst and depthfirst 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. 



Important Note..!
If you are not satisfied with above reply ,..PleaseASK HERE
So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this pagePossibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
Fast Search Strategies for Fractal Image Compression ppt  seminar flower  1  1,286 
23032013, 11:25 AM Last Post: Guest 

Searching and Sorting  seminar ideas  0  419 
26042012, 01:20 PM Last Post: seminar ideas 

SEARCHING ALGORITHMS  seminar class  0  929 
25042011, 02:23 PM Last Post: seminar class 

DiscreteEvent Simulation:A First Course  projectsofme  0  1,061 
07102010, 10:52 AM Last Post: projectsofme 