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

Feedback Vertex Set (Кирилл Елагин)
Seminar on parameterized algorithms

What: Lecture
When: Wednesday, 09 April 2014, 18:00–19:30
Where: ПОМИ РАН

Description

Мы познакомимся с техникой итеративного сжатия на примере задачи о поиске разрывающего множества вершин в турнире. Затем изучим некоторые продвинутые методы кернелизации и получим с помощью них квадратичное ядро для задачи о разрывающем множестве в произвольном неориентированном графе.