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

Параллельный алгоритм для построения паросочетаний
Randomized Algorithms

What: Lecture
When: Wednesday, 28 April 2021, 18:10–19:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

В этой лекции закончим доказательство теоремы Валианта-Варизани и построение параллельного алгоритма для нахождения совершенных паросочетаний, для чего мы будем использовать лемму Шварца-Зиппеля и изоляционную лемму.