An adjustable linear time parallel algorithm for maximum weight bipartite matching

We present a parallel algorithm for finding a maximum weight matching in general bipartite graphs with an adjustable time complexity of using O(nmax(2ω,4+ω)) processing elements for ω⩾1. Parameter ω is not bounded. This is the fastest known strongly polynomial parallel algorithm to solve this problem. This is also the first adjustable parallel algorithm for the maximum weight bipartite matching problem in which the execution time can be reduced by an unbounded factor. We also present a general approach for finding efficient parallel algorithms for the maximum matching problem.