Rozdíly

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

--- teaching:intro_par_alg2425 [2024/11/20 12:33] – [Material Covered] Jiří Fiala
+++ teaching:intro_par_alg2425 [2024/12/17 22:45] (aktuální) – 17. 12. Martin Koutecky
@@ Řádek 19: / Řádek 19: @@
 | 5. 11. | //sport day - no class//|
 | 12. 11. | Dynamic programming and convolutions on <typo fv:small-caps>Set Cover</typo> and <typo fv:small-caps>Steiner Tree</typo> **[PA 6.1]**, PIE and <typo fv:small-caps>Hamiltonian Cycle</typo> **[PA 10.1.1]** |
-| 29. 11. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**|
+| 19. 11. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**|
+| 26. 11. | More Treewidth - grids, bidimensionality **[PA 7.7.1, 7.7.2 ]**|
-/*| 30. 11. | More Treewidth - FPT alg., MSO, grids **[PA 7.7.1, 7.7.2 ]**|
+| 3. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded  $nd(G)$ . **[ND, NdCol, 5M]**|
-| 7. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded  $nd(G)$ . **[ND, NdCol, 5M]**|
+| 10. 12. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> via  $n$ -fold IP, and as a convex IP in small dimension **[5M, Thm 2(a), 2(b)]**|
-| 14. 12. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> 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 <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]**; <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.]]|
-| 21. 12. | Neighborhood diversity: finish <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]**|
+| 7. 1. | //Plan:  $P||C_{\max}$  is FPT( $d$ ) if  $p_{\max}$  unary bounded, using the algorithm of Goemans-Rothvoss **[GR]**. Another application: <typo fv:small-caps>Equitable Coloring</typo> is FPT( $nd(G)$ ).//|
-| 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: <typo fv:small-caps>Equitable Coloring</typo> is FPT( $nd(G)$ ). |*/
 ===== Materials =====