I came across a good problem in an algorithms textbook and I am not sure if my algorithm is correct or not.The problem goes like this:↵
↵
Given a tree T where every vertex is assigned a label which is a positive integer, describe an algorithm to find the largest rooted minor that is a minimum heap. Over here A rooted minor of a rooted tree T is any tree obtained by contracting one or more edges. When we contract an edge (u, v), where u is the parent of v, the children of v become new children of u and then v is deleted. From this we can see that the root of the tree should always be part of any rooted minor.↵
↵
↵
What would be an optimized algorithm, could anyone please explain the recurrence relation for the DP solution. Any help would be appreciated!.↵
↵
UPDATE: I have attached 2 possible solutions as comments, can someone verify the correctness please
↵
Given a tree T where every vertex is assigned a label which is a positive integer, describe an algorithm to find the largest rooted minor that is a minimum heap. Over here A rooted minor of a rooted tree T is any tree obtained by contracting one or more edges. When we contract an edge (u, v), where u is the parent of v, the children of v become new children of u and then v is deleted. From this we can see that the root of the tree should always be part of any rooted minor.↵
↵
↵
What would be an optimized algorithm, could anyone please explain the recurrence relation for the DP solution. Any help would be appreciated!.↵
↵
UPDATE: I have attached 2 possible solutions as comments, can someone verify the correctness please
