Parameterized complexity 2026: различия между версиями

Текущая версия от 15:08, 9 сентября 2026

Course name: parameterized algorithms and complexity

First lecture Sept 8th!

Lecture: Tuesday 9h30 -- 10h50 in D510 on sept 8th

Seminar: Tuesday 11h10 -- 12h30 in R405 on sept 8th

Both in class and in zoom. For attending on zoom, you must switch on the camera.

Invite link for telegram group for questions about materials and practical issues.

syllabus, with all information, reference books, ...

Table Caption (Optional)
Date	topic	notes	problem list !
08 sept	Classes FPT and XP, examples, kernels, vertex cover in time 1.4645^k k^{O(1)} + n^{O(1)}	01_notes.pdf	[01problems
15 sept	No lecture while students are still subscribing
22 sept	More vertex cover kernels: cut degree ≤ 3 nodes, linear programming (Nemhauser-Trotter thm + fast algorithm). A Kernel for set cover.

@@ Строка 24: / Строка 24: @@
 | 15 sept || No lecture while students are still subscribing ||  ||
 |-
-| 22 sept ||  More about vertex cover: kernelize degree ≤ 3 nodes, linear programming kernel and Nemhauser-Trotter theorem, VC above linear programming. A Kernel for set cover. || ||
+| 22 sept ||  More vertex cover kernels: cut degree ≤ 3 nodes, linear programming (Nemhauser-Trotter thm + fast algorithm). A Kernel for set cover. || ||
 |}