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

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

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

Место проведения: Computer Science клуб, наб. реки Фонтанки, д. 27
Регистрация на мероприятие обязательна

Реклама

Популярные мероприятия
Соглашение на обработку персональных данных