Difference between revisions of "TADM2E 5.13"
(Part 2) |
(quick description of the Red-black solution for problem 3.) |
||
| Line 2: | Line 2: | ||
2) We consider again the leafs, each is degree 1. For each leaf, if we consider its parent, its degree is the number of children + 1. It means that we have to choose between removing the n children of degree one or the parent of degree n+1. We remove the parent, mark the leafs as included, and recurse as in 1) above. | 2) We consider again the leafs, each is degree 1. For each leaf, if we consider its parent, its degree is the number of children + 1. It means that we have to choose between removing the n children of degree one or the parent of degree n+1. We remove the parent, mark the leafs as included, and recurse as in 1) above. | ||
| + | |||
| + | 3) We know we will be able to remove at most one every other node, so we use a two-coloring technique (Red/Black) and perform a post-order traversal. Let's assume we will remove all the Black node. When we process a node, we also store with each node the sum over its immediate children of the respective Red and Black weight for the subtree. | ||
| + | If not all of the children are Red, we need to mark the current node as Red. But we also have the option to reverse the coloring of all the Red-children's subtree. So we look at the sum over the red-children for | ||
| + | Red and Black, and compare the difference of these sum to the current node's weight. If the current node's weight is above, we swap the coloring for these subtree. | ||
| + | The current node will record the Black and Red sum of its children's subtree, and add its own weight to its color. | ||
Revision as of 01:20, 1 January 2017
1) We can determine that leafs should never be included into the cover. Therefore all leaves should be unmarked, which means that all of their parents should be marked. Now we remove all leaves from the tree and all of their parents, together with all of their edges. We then repeat this process on the modified tree.
2) We consider again the leafs, each is degree 1. For each leaf, if we consider its parent, its degree is the number of children + 1. It means that we have to choose between removing the n children of degree one or the parent of degree n+1. We remove the parent, mark the leafs as included, and recurse as in 1) above.
3) We know we will be able to remove at most one every other node, so we use a two-coloring technique (Red/Black) and perform a post-order traversal. Let's assume we will remove all the Black node. When we process a node, we also store with each node the sum over its immediate children of the respective Red and Black weight for the subtree. If not all of the children are Red, we need to mark the current node as Red. But we also have the option to reverse the coloring of all the Red-children's subtree. So we look at the sum over the red-children for Red and Black, and compare the difference of these sum to the current node's weight. If the current node's weight is above, we swap the coloring for these subtree. The current node will record the Black and Red sum of its children's subtree, and add its own weight to its color.
