Uživatelské nástroje

Nástroje pro tento web


teaching:intro_par_alg2425

Toto je starší verze dokumentu!


Introduction to Parameterized Algorithms 24/25

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.

Material Covered

date what was said [source]
1. 10. Introduction to parameterized algorithms / complexity. [PA 1]
8. 10. Kernelization [PA 2.1, 2.2.1, 2.3-intro, 2.3.1]. Crown decomposition lemma proof was from [Ker, Lemma 4.5]
15. 10. FPT algorithm for Vertex Cover above LP [PA 3.4],
22. 10. 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]
29. 10. Iterative Compression for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal, [PA 4.1, 4.3.1, 4.4]

Materials

teaching/intro_par_alg2425.1730189843.txt.gz · Poslední úprava: 2024/10/29 09:17 autor: Jiří Fiala