Лекция 11. Параллельный алгоритм для построения паросочетаний

Лекция №11 курса «Рандомизированные алгоритмы», весна 2021 (Новосибирск). В этой лекции закончим доказательство теоремы Валианта-Варизани и построение параллельного алгоритма для нахождения совершенных паросочетаний, для чего мы будем использовать лемму Шварца-Зиппеля и изоляционную лемму. Преподаватель курса: Рене Андреасович ван Беверн, заведующий лабораторией алгоритмики ММФ НГУ, старший преподаватель ММФ НГУ. Подробное описание занятия: