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

Вероятностные методы при построении параметризованных алгоритмов
Параметризованные алгоритмы


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

Описание

Метод раскраски при построении вероятностных параметризованных алгоритмов. Кодирование цветом(Color Coding). Вероятностное разделение(Random Separation). Задачи:

  1. Задача о разрезании контуров \(4^k n^{O(1)}\).
  2. Задача о \(k\)-пути методом кодирования цветом \(2^k n^{O(1)}\).
  3. Задача о изоморфном подграфе в графах ограниченной степени за время \(2^{dk}k!n^{O(1)}\), где \(d\) это максимальная степень графа.

Видео