daneshtoshniwal's blog

By daneshtoshniwal, history, 6 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it