Feedback Vertex Set

Докладчик: 
Кирилл Елагин
Дата: 
Wednesday, April 9, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

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