This was very helpful, thanks. just a thought : since the sub-trees are disjoint, isn't this rather just a divide and conquer algorithm? Why is it dynamic? There needs to be some Bellman relation that computes the max IS value for a certain node using the value for sub trees more than once, somehow i fail to see it. Thanks for the video.
Isn’t the simple greedy algorithm guaranteed to provide correct results on trees? Select node with smallest degree (greater than 0), remove connected nodes, repeat until every node is connected.
Thanks bro I am a 2nd year CSE student from IIIT Delhi ..this is very logical explanation with dp involved
"..in fact this problem is so important that I deal with it in my research.." 😊
Extremely helpful, thanks!!!
This was very helpful, thanks. just a thought : since the sub-trees are disjoint, isn't this rather just a divide and conquer algorithm? Why is it dynamic? There needs to be some Bellman relation that computes the max IS value for a certain node using the value for sub trees more than once, somehow i fail to see it. Thanks for the video.
thank you bro
Isn’t the simple greedy algorithm guaranteed to provide correct results on trees?
Select node with smallest degree (greater than 0), remove connected nodes, repeat until every node is connected.
Ok, that wouldn’t be a linear time algorithm 😊.
Thanks for your content, learned a lot!
very helpful
thank you