English subtitles

← 11-20 Properties Of Search Tree Construction

Get Embed Code
1 Language

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

  1. I would like you to think about a few properties of constructing the search tree this way,
  2. so taking an edge that is not yet covered--
  3. so where both endpoints are not part of the vertex cover--
  4. and then branching into 3 different possibilities, putting 1 endpoint into the vertex cover,
  5. putting the other point into the vertex cover, or both.
  6. So will the search tree always find the smallest vertex cover?
  7. Of course it can also find larger ones, but will it always find the smallest possible one
  8. for any given graph?
  9. Or could there be special cases where the search tree is wrong
  10. and we still need to fix that?
  11. Is it that the search tree at each level--and by level I basically mean if this is the tree here,
  12. then this would be a level and this would be the next level--
  13. is it that at each level the algorithm determines the assignment?
  14. So is a vertex in the vertex cover or not for at least 1 vertex?
  15. And this will require some thought, so this is a challenging one down here.
  16. Can we construct the search tree so that at each level of the search tree
  17. we determine the assignment of at least 2 vertices?
  18. And of course you could just guess here,
  19. but I would really like you to spend some time and think about the answers
  20. because this will be very important for you to really understand
  21. how you can build better search trees.