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

Цветовое и хроматическое кодирование (Павел Чуприков)
Семинар по параметризованным алгоритмам


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

Описание

Поиск ориентриованного \( k \)-цикла за среднее время \( 2^{O(k)}V^\omega \), и \( 2^{O(k)}V^\omega \log V \) — в худшем случае. Поиск взвешенного множества дуг обратной связи в турнире за \( 2^{O(\sqrt{k}\log k)} + n^{O(1)} \) среднее и худшее время.