Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:intro_par_alg2526 [2025/11/04 22:36] – Martin Koutecky | teaching:intro_par_alg2526 [2025/11/10 15:10] (aktuální) – Martin Koutecky |
|---|
| | 20. 10. | FPT algorithms for <typo fv:small-caps>Feedback Vertex Set</typo> in $\mathcal{O}^*((3k)^k)$ time and for <typo fv:small-caps>Vertex Cover above LP in $\mathcal{O}^*(4^d)$ **[PA 3.3, 3.4]**</typo>| | | 20. 10. | FPT algorithms for <typo fv:small-caps>Feedback Vertex Set</typo> in $\mathcal{O}^*((3k)^k)$ time and for <typo fv:small-caps>Vertex Cover above LP in $\mathcal{O}^*(4^d)$ **[PA 3.3, 3.4]**</typo>| |
| | 27. 10. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| | | 27. 10. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| |
| | 3. 11. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> as a convex IP in small dimension, and later as $n$-fold IP **[5M, Thm 2(a), 2(b)]**; <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]** as small-dim IP with convex constraints.| | | 3. 11. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> as a convex IP in small dimension, and later as $n$-fold IP **[5M, Thm 2(a), 2(b)]**; <typo fv:small-caps>Capacitated Dominating Set</typo> as small-dim IP with convex constraints. **[5M, Thm 1]**| |
| | | 10. 11. | $P/Q/R||C_{\max}$ via $n$-fold IP recap. How does the FPT $n$-fold IP algo work (birds-eye view). Borda-<typo fv:small-caps>Shift Bribery</typo> is FPT($m$) via $n$-fold IP.| |
| |
| /* | /* |
