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