Week 6 · Dynamic programming on tree decompositions

Nice tree decompositions support algorithms such as maximum-weight independent set and dynamic programming on bounded-treewidth graphs.

Lectures

• Nice Tree Decomposition and Algorithm for Max Weight Independent Set

• Dynamic Programming Algorithm over graphs of Bounded Treewidth

Official NPTEL lecture index