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

Материал из SEWiki
Перейти к: навигация, поиск
(Практика)
(Лекции)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 15: Строка 15:
 
*20 april. Important cuts. Edge Multiway Cut.
 
*20 april. Important cuts. Edge Multiway Cut.
 
*27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.
 
*27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.
 +
*04 may. W[1] class.
 +
*11 may. Kernel lower bounds.
 +
*18 may. Vertex cover does not admit subquadratic bit size kernel.
  
 
== Практика ==
 
== Практика ==
Строка 34: Строка 37:
 
*[[Медиа:FPT-home-9.pdf|27 april, "Important cuts II(HW)."]]
 
*[[Медиа:FPT-home-9.pdf|27 april, "Important cuts II(HW)."]]
 
*[[Медиа:FPT-class-10.pdf|03 may, "W[1], W[2]."]]
 
*[[Медиа:FPT-class-10.pdf|03 may, "W[1], W[2]."]]
*[[Медиа:FPT-class-10.pdf|03 may, "W[1], W[2](HW)."]]
+
*[[Медиа:FPT-home-10.pdf|03 may, "W[1], W[2](HW)."]]

Текущая версия на 18:32, 3 июня 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 .
  • 30 march. Randomized methods.
  • 6 april. algorithm for k-path. Derandomization.
  • 13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.
  • 20 april. Important cuts. Edge Multiway Cut.
  • 27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.
  • 04 may. W[1] class.
  • 11 may. Kernel lower bounds.
  • 18 may. Vertex cover does not admit subquadratic bit size kernel.

Практика

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