Rozdíly

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

--- teaching:intro_par_alg2324 [2023/12/07 12:04] – Martin Koutecky
+++ teaching:intro_par_alg2324 [2024/01/11 17:54] (aktuální) – lecture 11. 1. Martin Koutecky
@@ Řádek 21: / Řádek 21: @@
 | 30. 11. | More Treewidth - FPT alg., MSO, grids **[PA 7.7.1, 7.7.2 ]**|
 | 7. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**|
+| 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)]**|
+| 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]**|
+| 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)$). |
   * **[PA]** is the book [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf| Parameterized Algorithms]].
@@ Řádek 26: / Řádek 30: @@
   * **[NdCol]** [[https://rdcu.be/cUrsc|A note on coloring...]]: a paper by Martin which retells the coloring algorithm by Lampis and points out that it can be solved more efficiently
   * **[5M]** [[https://www.sciencedirect.com/science/article/pii/S157252862030030X?ref=pdf_download&fr=RR-2&rr=8317fd563de2b333|Integer programming in parameterized complexity: Five miniatures]] a comprehensive paper about various parameterized integer programming algorithms and their applications to problems on bounded-$nd$ graphs.
+  * **[GR]** [[https://dl.acm.org/doi/10.1145/3421750|Polynomiality for Bin Packing with a Constant Number of Item Types]]