teaching:intro_par_alg2324
Toto je starší verze dokumentu!
Introduction to Parameterized Algorithms 23/24
Tutorial sessions
Tutorials are led by Tung. Click here for the website of the tutorials, where you can find materials from the tutorial sessions and instructions on how to solve homework.
date | what was said [source] |
---|---|
5. 10. | Introduction to parameterized algorithms / complexity. [PA 1] |
12. 10. | Kernelization [PA 2.1, 2.2.1, 2.3-intro, 2.3.1, 2.5 without Lemma 2.22] |
19. 10. | Finishing kernels from last time. Bounded Search Trees: Vertex Cover in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; Closest String in $\mathcal{O}^*(d^d)$ time [PA 3.1, 3.5] |
26. 10. | FPT algorithm for Vertex Cover above LP, application: FPT algorithm for Odd Cycle Transversal [PA 3.4]; |
2. 11. | No class: Dean's sport day |
9. 11. | Iterative Compression for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal, [PA 4.1, 4.3.1, 4.4] |
16. 11. | Dynamic programming and convolutions on Set Cover and Steiner Tree [PA 6.1], PIE and Hamiltonian Cycle [PA 10.1.1] |
23. 11. | Treewidth, nice tree decompositions, Independent Set [PA 7.2, 7.3.1] |
30. 11. | Plan: More Treewidth - FPT alg., MSO, grids [PA 7.7.1, 7.7.2 ] |
[PA] is the book Parameterized Algorithms.
teaching/intro_par_alg2324.1700841799.txt.gz · Poslední úprava: 2023/11/24 17:03 autor: Jiří Fiala