Studying for my algorithms test by spamming Algorithm Design Manual exercises, but I’m stuck on this one. I know I have to keep score somehow.
Let
G = (V,E)be a tree with arbitrary weights associated with the vertices.Give an efficient algorithm to find a minimum-weight vertix cover of
G.
Some of my thoughts:
- The leaf’s parents (lets call it p) should be picked because they are usually more efficient. Then mark all p.parents to be “covered”. Then you are left with a smaller tree. But there are counter examples to this, since it’s weighted. This is only true for unweighted graphs.
Also, I am confused about part 3. of this solution given by Skiena. Could someone explain this to me? And also part 4., what does “backtracking” the score mean?
5