MA015 Graph Algorithms
Lecture V - Dynamic Programming for Hard Problems
Dates
16.11. (dynamic programming on trees and circular-arc graphs)
23.11. (tree decompositions and tree-width, algorithm for max-weight independent set)
30.11 (algorithm for 3-colouring, computing nice tree decompositions and tree decompositions)
Reading
Kleinberg, Tardos: Algorithm Design [PDF]
Additional material
If you want to know more, or want to look a t 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/podzim2015/MA015/um/05-trees.pdf