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


Что: Лекция
Когда: Пятница, 25 ноября 2016, 19:00–20:20
Где: ПОМИ РАН, аудитория 106

Описание

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