Trees · Dynamic Programming
Lesson 2
An important property of trees, often used when designing efficient algorithms for computational problems on trees:
If you remove a vertex of degree at least two from a tree, the tree will break into independent parts.We will demonstrate this property using the problem of finding a maximum independent set in a graph. In general, this is a hard algorithmic problem. However, if it is additionally known that the input graph is a tree, the problem can be solved in linear time (relative to the size of the graph)!