Combining Breadth-First and Depth-First Strategies in Searching for Treewidth
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
project report helper
Active In SP
**

Posts: 2,270
Joined: Sep 2010
#1
12-10-2010, 10:58 AM



.pdf   dfs and bfs.pdf (Size: 501.4 KB / Downloads: 72)
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.
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK 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 page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Fast Search Strategies for Fractal Image Compression ppt seminar flower 1 1,276 23-03-2013, 11:25 AM
Last Post: Guest
  Searching and Sorting seminar ideas 0 415 26-04-2012, 01:20 PM
Last Post: seminar ideas
  SEARCHING ALGORITHMS seminar class 0 925 25-04-2011, 02:23 PM
Last Post: seminar class
Thumbs Up Discrete-Event Simulation:A First Course projectsofme 0 1,057 07-10-2010, 10:52 AM
Last Post: projectsofme