English subtitles

← 12-10 Search Tree Branches

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. How do we use pre-processing. We know that we can find structures like these in our graph.
  2. And here can be other connections possibly--it don't have to be, but we'll ignore those for now.
  3. Now, if we look at this structure from a brute force perspective, there are eight different possibilities
  4. for assigning or not assigning these vertices here into a vertex cover.
  5. The eight possibilities are as follows: either we can take no vertex at all into the vertex cover
  6. and you already know that this going to cause a problem and we could take all of them
  7. into the vertex cover, and then then the six more combinations.
  8. A brute force search tree would look at eight possible assignments.
  9. Out of these eight assignments, if you were to design a search tree that directly
  10. branches into these cases here, there's only five cases that would even make sense.
  11. Please check which of these cases would make sense for a search tree.