Where can I find a parallel algorithm for finding the maximum matching in a graph?

Question

Algorithms

Greetings!
Is there a resource on the Internet where you can see a parallel algorithm for finding the maximum matching in a graph?

Answer 1

(if we are talking about a bipartite graph)
Look for parallel dfs or parallel maximum flow.
Actually, I have never seen parallelization of the search for matchings. Too specific task.
However, there is a search algorithm through the maximum flow.
If we add a source connected to the left side and a source connected to the right side to the graph, and make the capacities 1 each, then any flow here will be equivalent to a matching. There is the Ford-Folkerson algorithm , where the main work is to do dfs in a graph to find a path from source to sink. Actually, you can parallelize this dfs. This is a more popular task and the algorithms are easy to google.
There will be no full parallelization here, because dfs is launched sequentially n times and they cannot be started in parallel, because after each dfs the graph changes.

Answer 2

Interest Ask. Kmk Ford-Fulkerson is either poorly parallelized. Or, after parallelism, it will sag in blocking vertices and edges, which will make it worse in terms of efficiency than non-parallel.
Here you have to think.