MA015 Graph Algorithms
Lecture V - Dynamic Programming for Hard Problems
Dates
7.11. (dynamic programming on trees)
14.11. dynamic programming on trees and circular-arc graphs; treewidth
21.11. dynamic programming on tree decompositions; nice tree decompositions
Reading
Kleinberg, Tardos: Algorithm Design [PDF]
Algorithm for Vertex Cover on tree decompositions:
R. Niedermayer: Invitation to Fixed-Parameter Algorihtms: [PDF]
Additional material
If you want to know more, or want to look at things from a slightly different, more theoretical angle, Jiri Fiala (MFF UK) has a nice text called Graph minors, decompositions and algorithms
Slides
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/1433/podzim2016/MA015/um/05-trees.pdf