Поиск совершенных паросочетаний в регулярных двудольных графах

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