Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Нижние оценки. Класс W[1]
Параметризованные алгоритмы

Что: Лекция
Когда: Среда, 09 декабря 2015, 18:00–19:30
Где: ПОМИ РАН
Слайды: parameterizedalgorithms_lecture_091215.pdf

Описание

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

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

Видео