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

Версия 19:44, 2 апреля 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 ${\displaystyle O^*(4^k)}$. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal ${\displaystyle O^*(3^k)}$.

Практика

• 16 february, "Bounded search trees (HW)."

Надо оформить 5 самых сложных задач из Вами решенных.

• 2 march, "Kernelization."
• 2 march, "Kernelization(HW)."
• 16 march, "Kernelization II(HW)."
• 23 march, "Iterative Compression."
• 23 march, "Iterative Compression(HW)."
• 30 march, "Randomized methods."
• 30 march, "Randomized methods(HW)."