Параметризованные алгоритмы. Лекция 3
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
23.09.15
Дата публикации:
07.10.15
Код для блога:
Кернелизация, построение ядер. КГТ-разложением(разложение короной, Crown Decomposition), лемма о подсолнухах(Sunflower lemma). Построение ядер с помощью линейного программирования.
- Ядро размера 3k для Vertex Cover (КГТ-разложение)
- Ядро для задачи о максимальной выполнимости: k переменных, 2k клозов (КГТ-разложение)
- Ядро для d-Hitting Set c d!kdмножествами
- Ядро с 2k вершинами для задачи о вершинном покрытии (линейное программирование)
Другие лекции курса
13