| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429284 | Information Processing Letters | 2006 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
