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

Question

[ddd329]

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

Comments

[Сергей Соколов]

Плиска ммаксимальной биклики? Где каждый из А с каждым из Б.

Answer 1

[Wataru]

(если речь про двудольный граф)

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

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

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

Полной параллелизации тут не будет, потому что dfs запускается последовательно n раз и их нельзя параллельно пускать, ведь после каждого dfs-а граф меняется.

Comments

[ddd329]

wataru,

(если речь про двудольный граф)

.
Да, речь именно о нем.

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

Я вот тоже не видел, но наткнулся на такой документ, который является частью дипломной работы.

[Wataru]

Весьма странный документ. Во первых, там утверждается, что с обходом в ширину алгоритм Куна получает n*2.5 сложность, но это уже будет алгоритм Хопкрафта-Карпа.

А главное, там параллелизация делается по данным и отсутствует какое-либо объяснение, как они этого добились. Как будто, там граф разбивается на много независимых областей. Проблема только в том, что, если граф связен, таких независимых областей вообще нет. Но у них там граф случайный и с очень маленьким количеством ребер. Т.ч. вполне возможно, что там куча мелких несвязанных между собой компонент. Это очень крайний случай (найдите паросочетание в куче мелких графов сразу). Вся идея - запустить один и тот же алгоритм Куна кучу раз параллельно.

Еще там какой-то бред про итоговую линейную сложность(?!).

В общем, качество этого документа весьма сомнительное. Обычная курсовая работа ради зачета. Пользы и новизны почти нет. Все идеи тривиальные, но расписано так, чтобы это не бросалось в глаза.

[ddd329]

wataru, спасибо!

[ddd329]

wataru, вот кстати интересный документ
Как думаете он может помочь в решении моего вопроса?

[Wataru]

ddd329, А вот это - хорошая статья.

Ничего особо революционного там нет - просто вместо DFS дополняющие пути ищутся через BFS. Но там есть интересная эвристика, которая не влияет на асимптотическую сложность, но на некоторых графах хорошо ускоряет работу алгоритма: бфс не запускается заново каждый раз, некоторая часть с предыдущего обхода переиспользуется.

Заодно там уделяется внимание, собственно, паралелизации и в описании алгоритма указано, какие операции надо делать с локами/атомиками. Думаю, это именно то, что вы ищете.

[ddd329]

wataru, спасибо большое! Буду пробовать)

Answer 2

[mayton2019]

Интересный вопрос. Кмк форд-фалкерсон либо плохо параллелится. Либо после параллелизма просядет в блокировках вершин и ребер, что сделает его худшим по эффективности чем непараллельный.

Тут надо подумать.