algorithm - Minimum-size vertex cover of tree: Dynamic Programming Formulation -
i'm trying understand how formulate problem of finding minimum-size vertex cover of tree dynamic programming problem , having trouble. me non-dynamic programming formulation involving depth-first search makes intuitive sense. involves doing dfs leaf nodes, including parent nodes in minimum size vertex cover, , repeating root. pseudocode this: // dfs based solution find_minimum_vertex_cover_dfs(root) { // leaf nodes aren't in minimum size vertex cover if (root == null || isleafnode(root)) { return; } (each child node of root) { find_minimum_vertex_cover_dfs(child node); // child isn't in minimum size vertex cover need cover edge // current root child including current root if (!isinmincover(child node)) { include root in minimum vertex cover; } } } the dynamic programming formulation got here follows: dynamicvc(root): each child c: best[c][0], best[c][1] = dynamicvc(c) ...