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

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

Пожалуйста, представьтесь:

E-mail:

Код защиты от спама: captcha

Если Вы цитируете отзыв, опубликованый на другом сайте, пожалуйста, укажите адрес страницы, на которой размещен цитируемый отзыв:

Получать уведомления о других отзывах.

Реклама

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