MA015 Graph Algorithms

Lecture V - Dynamic Programming for Hard Problems

Dates

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/podzim2017/MA015/um/05-trees.pdf