Uživatelské nástroje

Nástroje pro tento web


teaching:intro_par_alg2627

Toto je starší verze dokumentu!


Introduction to Parameterized Algorithms 26/27

Tutorial sessions

Tutorials are led by Martin Koreček, 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] I mentioned this connection between parameterized and exponential algorithms
9. 10. Kernelization [PA 2.1, 2.2.1, 2.3-intro, 2.3.1], Crown decomposition| /* | 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]
5. 11. sport day - no class
12. 11. Dynamic programming and convolutions on Set Cover and Steiner Tree [PA 6.1], PIE and Hamiltonian Cycle [PA 10.1.1]
19. 11. Treewidth, nice tree decompositions, Independent Set [PA 7.2, 7.3.1]
26. 11. More Treewidth - grids, bidimensionality [PA 7.7.1, 7.7.2 ]
3. 12. Intro to neighborhood diversity and ILPs. Solving Coloring on graphs of bounded $nd(G)$. [ND, NdCol, 5M]
10. 12. Neighborhood diversity: Sum Coloring via $n$-fold IP, and as a convex IP in small dimension [5M, Thm 2(a), 2(b)]
17. 12. Plan: Neighborhood diversity: Q&A on Sum Coloring [5M, Thm 2], Capacitated Dominating Set [5M, Thm 1]; Max $q$-Cut [5M, Thm 3]. Geogebra: $x \cdot y$ is obviously not convex.
7. 1. Plan: $P||C_{\max}$ is FPT($d$) if $p_{\max}$ unary bounded, using the algorithm of Goemans-Rothvoss [GR]. Another application: Equitable Coloring is FPT($nd(G)$).

*/

Materials

teaching/intro_par_alg2627.1791571217.txt.gz · Poslední úprava: autor: Jiří Fiala