TADM2E 5.13 - Revision history

Matt: Undo revision 1062 by FuckMatt (talk)

2020-08-01T01:02:07Z

Undo revision 1062 by FuckMatt (talk)

FuckMatt: Blanked the page

2020-07-31T09:36:58Z

Blanked the page

Matt: Undo revision 846 by Mgits (talk)

2020-07-23T15:53:47Z

Undo revision 846 by Mgits (talk)

Mgits at 00:17, 20 July 2020

2020-07-20T00:17:51Z

Joky: quick description of the Red-black solution for problem 3.

2017-01-01T01:20:59Z

quick description of the Red-black solution for problem 3.

Joky: Part 2

2017-01-01T00:43:56Z

Part 2

Cptsudoku at 15:41, 25 March 2015

2015-03-25T15:41:09Z

Cptsudoku at 15:16, 25 March 2015

2015-03-25T15:16:02Z

Cptsudoku at 15:15, 25 March 2015

2015-03-25T15:15:19Z

Cptsudoku: Created page with "(a) We can determine that leaf 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..."

2015-03-25T15:04:31Z

Created page with "(a) We can determine that leaf 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..."

New page

(a) We can determine that leaf 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.

← Older revision	Revision as of 01:02, 1 August 2020
Line 1:	Line 1:
	+	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.

← Older revision		Revision as of 09:36, 31 July 2020
Line 1:		Line 1:
−	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.~~

← Older revision		Revision as of 15:53, 23 July 2020
Line 1:		Line 1:
−	--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) ~~00:17~~, ~~20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC~~)~~--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, ~~20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC~~)~~--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]~~) ~~00:17~~, ~~20 July 2020 (UTC)-~~-~~[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020~~ (~~UTC~~)-~~-[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC)~~--~~[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, ~~20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17~~, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)	+	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.

← Older revision		Revision as of 00:17, 20 July 2020
Line 1:		Line 1:
−	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.~~	+	--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)--[[User:Mgits\|Mgits]] ([[User talk:Mgits\|talk]]) 00:17, 20 July 2020 (UTC)
−
−	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.~~

← Older revision		Revision as of 01:20, 1 January 2017
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.

← Older revision		Revision as of 00:43, 1 January 2017
Line 1:		Line 1:
−	(a) We can determine that ~~leaf~~ 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.	+	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.

← Older revision		Revision as of 15:41, 25 March 2015
Line 1:		Line 1:
	(a) We can determine that leaf 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.		(a) We can determine that leaf 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.
−
−	~~(b) Since the degree of the parent of a leaf is sum of degrees of all leaves + 1 we see that, again, the leaves should be left unmarked. The process after that, as shown above, is straightforward.~~

← Older revision		Revision as of 15:16, 25 March 2015
Line 1:		Line 1:
	(a) We can determine that leaf 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.		(a) We can determine that leaf 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.
		+
	(b) Since the degree of the parent of a leaf is sum of degrees of all leaves + 1 we see that, again, the leaves should be left unmarked. The process after that, as shown above, is straightforward.		(b) Since the degree of the parent of a leaf is sum of degrees of all leaves + 1 we see that, again, the leaves should be left unmarked. The process after that, as shown above, is straightforward.

← Older revision		Revision as of 15:15, 25 March 2015
Line 1:		Line 1:
	(a) We can determine that leaf 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.		(a) We can determine that leaf 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.
		+	(b) Since the degree of the parent of a leaf is sum of degrees of all leaves + 1 we see that, again, the leaves should be left unmarked. The process after that, as shown above, is straightforward.