teaching:intro_par_alg2324
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Následující verze | Předchozí verze | ||
teaching:intro_par_alg2324 [2023/10/02 13:10] – vytvořeno Martin Koutecky | teaching:intro_par_alg2324 [2024/01/11 17:54] (aktuální) – lecture 11. 1. Martin Koutecky | ||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
====== Introduction to Parameterized Algorithms 23/24 ====== | ====== Introduction to Parameterized Algorithms 23/24 ====== | ||
+ | |||
+ | |||
+ | ===== Tutorial sessions ===== | ||
+ | |||
+ | Tutorials are led by [[https:// | ||
+ | [[https:// | ||
+ | you can find materials from the tutorial sessions and instructions on how to solve homework. | ||
+ | |||
+ | |||
+ | {{tablelayout? | ||
+ | ^ 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: <typo fv: | ||
+ | | 26. 10. | FPT algorithm for <typo fv: | ||
+ | | 2. 11. | **No class: [[https:// | ||
+ | | 9. 11. | Iterative Compression for <typo fv: | ||
+ | | 16. 11. | Dynamic programming and convolutions on <typo fv: | ||
+ | | 23. 11. | Treewidth, nice tree decompositions, | ||
+ | | 30. 11. | More Treewidth - FPT alg., MSO, grids **[PA 7.7.1, 7.7.2 ]**| | ||
+ | | 7. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv: | ||
+ | | 14. 12. | Neighborhood diversity: <typo fv: | ||
+ | | 21. 12. | Neighborhood diversity: finish <typo fv: | ||
+ | | 4. 1. | Parameterized reductions, The W-hierarchy **[PA, 13.1, 13.2, 13.3]**| | ||
+ | | 11. 1. | $P||C_{\max}$ is FPT($d$) if $p_{\max}$ unary bounded, using the algorithm of Goemans-Rothvoss **[GR]**. Another application: | ||
+ | |||
+ | * **[PA]** is the book [[https:// | ||
+ | * **[ND]** [[https:// | ||
+ | * **[NdCol]** [[https:// | ||
+ | * **[5M]** [[https:// | ||
+ | * **[GR]** [[https:// | ||
+ | |||
+ |
teaching/intro_par_alg2324.1696245031.txt.gz · Poslední úprava: 2023/10/02 13:10 autor: Martin Koutecky