Uživatelské nástroje

Nástroje pro tento web


teaching:intro_par_alg2425

Rozdíly

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

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze
Předchozí verze
teaching:intro_par_alg2425 [2024/11/26 10:33] – [Material Covered] Tung Anh Vuteaching:intro_par_alg2425 [2024/12/17 22:45] (aktuální) – 17. 12. Martin Koutecky
Řádek 20: Řádek 20:
 | 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]** | | 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]** |
 | 19. 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 - gridsbidimensionality **[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> **[5MThm 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 **[PA13.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 ===== ===== Materials =====
teaching/intro_par_alg2425.1732613634.txt.gz · Poslední úprava: 2024/11/26 10:33 autor: Tung Anh Vu