Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:intro_par_alg2526 [2025/09/29 10:26] – vytvořeno Martin Koutecky
+++ teaching:intro_par_alg2526 [2025/11/10 15:10] (aktuální) – Martin Koutecky
@@ Řádek 12: / Řádek 12: @@
 {{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}}
 ^ date ^ what was said [source] ^
-| 1. 10. | Introduction to parameterized algorithms / complexity. **[PA 1]**|
+| 29. 9. | 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]**|
+| 6. 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 <typo fv:small-caps>Vertex Cover above LP **[PA 3.4]**</typo>,|
+| 13. 10. | Bounded Search Trees: <typo fv:small-caps>Vertex Cover</typo> in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; <typo fv:small-caps>Closest String</typo> in $\mathcal{O}^*(d^d)$ time **[PA 3.1, 3.5]** |
-| 22. 10. | Bounded Search Trees: <typo fv:small-caps>Vertex Cover</typo> in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; <typo fv:small-caps>Closest String</typo> in $\mathcal{O}^*(d^d)$ time **[PA 3.1, 3.5]** |
+| 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]**|
+| 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.|
+/*
+| 17. 12. | Plan: Neighborhood diversity: Q&A on <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, ; <typo fv:small-caps>Max $q$-Cut</typo> **[5M, Thm 3]**. [[https://www.geogebra.org/calculator/pfdttsng|Geogebra: $x \cdot y$ is obviously not convex.]]|
 | 29. 10. | Iterative Compression for <typo fv:small-caps>Vertex Cover</typo>, <typo fv:small-caps>Feedback Vertex Set</typo> and <typo fv:small-caps>Odd Cycle Transversal</typo>, **[PA 4.1, 4.3.1, 4.4]** |
 | 5. 11. | //sport day - no class//|