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
teaching:intro_par_alg2425 [2024/12/11 00:49] Martin Kouteckyteaching:intro_par_alg2425 [2024/12/17 22:45] (aktuální) – 17. 12. Martin Koutecky
Řádek 23: Řádek 23:
 | 3. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| | 3. 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)]**| | 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)]**|
-| 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]**//| +| 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.]]
- +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)$).//|
-/* +
-| 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]**| +
-| 41. | 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 ===== ===== Materials =====
teaching/intro_par_alg2425.1733874586.txt.gz · Poslední úprava: 2024/12/11 00:49 autor: Martin Koutecky