Параметризованные алгоритмы весна 2018 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Лекции)
(Лекции)
Строка 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 самых сложных задач из Вами решенных.