Combining Breadth-First and Depth-First Strategies in Searching for Treewidth
#1

[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.
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
Popular Searches: on course strategies for college, summer internship 2013 for b tech mechanical first year, first college for the, facial feature extraction with a depth aam algorithm ppt slides, physics practical reading of btech first year, the first flying train in history, mini project topics for electronics and communication for first year,

[-]
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
  ROBOTIC SURGERY AND TELE-SURGERY: BASIC PRINCIPLES AND DESCRIPTION OF A NOVEL CONCEPT projectsofme 1 2,855 27-02-2012, 01:12 PM
Last Post: seminar paper
  IP Authoring and Integration for HW/SW Co-Design and Reuse seminar class 0 1,401 05-05-2011, 11:07 AM
Last Post: seminar class
  SEARCHING ALGORITHMS seminar class 0 1,529 25-04-2011, 02:23 PM
Last Post: seminar class
  Using the iPhone and iPod Touch for Remote Sensor Control and Data Acquisition project report helper 0 2,028 19-10-2010, 01:05 PM
Last Post: project report helper
Thumbs Up Discrete-Event Simulation:A First Course projectsofme 0 1,685 07-10-2010, 10:52 AM
Last Post: projectsofme

Forum Jump: