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

Поиск паросочетания в регулярных двудольных графах (Николай Карпов)
Sublinear alhorithms

What: Lecture
When: Friday, 25 November 2016, 19:00–20:20
Where: ПОМИ РАН, аудитория 106

Description

Мы рассмотрим задачу поиска паросочетания в регулярных двудольных графах. Обсудим результаты по этой задаче и её применения. Рассмотрим рандомизированный алгоритм поиска последнего с сублинейным временем работы и докажем нижнюю оценку на время работы любого детерминированного алгоритма.