City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Нижние оценки. Класс W[1]
Parameterized Algorithms

What: Lecture
When: Wednesday, 09 December 2015, 18:00–19:30
Where: ПОМИ РАН
Slides: parameterizedalgorithms_lecture_091215.pdf

Description

Параметризованное сведение задачи $A$ к задаче $B$, где $(A,B)$ это следующие пары:

  1. Задача о клике, задача о клике в регулярных графах
  2. Задача о клике в регулярных графах, задача о разноцветной клике в регулярных графах
  3. Независимое множество в регулярных графа, задача о частичном вершинном покрытии
  4. Разноцветное независимое множество, задача о доминирующем множестве
  5. Задача о доминирующем множестве, задача о покрытии множествами
  6. Задача о покрытии множествами, задача о доминирующем множестве в графах-турнирах

Video