@ddd329

Где найти параллельный алгоритм нахождения максимального паросочетания в графе?

Приветствую!
Есть ли в интернете ресурс где можно посмотреть параллельный алгоритм нахождения максимального паросочетания в графе?
  • Вопрос задан
  • 249 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
(если речь про двудольный граф)

Ищите parallel dfs или parallel maximum flow.

Собственно, параллелизации поиска паросочетаний я нигде не видел. Слишком специфичная задача.

Однако, есть алгоритм поиска через максимальный поток.
Если добавить в граф исток, соединенный с левой долей, и исток, соединенный с правой долей, а пропускные способности сделать по 1, то любой поток тут будет равнозначен паросочетанию. Есть алгоритм Форда-фолкерсона, там основная работа - это делать dfs в графе для поиска пути из истока в сток. Собственно, можно распараллелить этот dfs. Это более популярная задача и алгоритмы гуглятся легко.

Полной параллелизации тут не будет, потому что dfs запускается последовательно n раз и их нельзя параллельно пускать, ведь после каждого dfs-а граф меняется.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
mayton2019
@mayton2019
Bigdata Engineer
Интересный вопрос. Кмк форд-фалкерсон либо плохо параллелится. Либо после параллелизма просядет в блокировках вершин и ребер, что сделает его худшим по эффективности чем непараллельный.

Тут надо подумать.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы