Параметризованные алгоритмы весна 2018 — различия между версиями
Материал из SEWiki
Bliznets (обсуждение | вклад) (→Лекции) |
Bliznets (обсуждение | вклад) (→Лекции) |
||
| Строка 8: | Строка 8: | ||
**Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability. | **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability. | ||
*16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching. | *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching. | ||
| − | *23 march. Iterative Compression. | + | *23 march. Vertex Cover above Matching. Iterative Compression. |
| + | ** Odd Cycle transversal <math>O^*(4^k)</math>. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal <math>O^*(3^k)</math>. | ||
== Практика == | == Практика == | ||
Версия 01:19, 26 марта 2018
Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)
Лекции
- 16 february. Bounded search trees.
- FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.
- 2 march. Kernelization.
- Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.
- 16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.
- 23 march. Vertex Cover above Matching. Iterative Compression.
- Odd Cycle transversal . Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal .
Практика
Надо оформить 5 самых сложных задач из Вами решенных.
