Name
Abstract | ||
|---|---|---|
We present a parallel algorithm for finding a maximum weight matching in general bipartite graphs with an adjustable time complexity of O(n/ω) 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.ipl.2005.10.013 | Inf. Process. Lett. |
Keywords | Field | DocType |
parallel algorithm,adjustable linear time parallel,execution time,maximum matching problem,adjustable parallel algorithm,maximum weight bipartite matching,general approach,efficient parallel algorithm,adjustable time complexity,maximum weight,graph algorithms,polynomial parallel algorithm,maximum weight bipartite,bipartite matching,parallel algorithms,time complexity,linear time,maximum matching | Discrete mathematics,Combinatorics,Parallel algorithm,Bipartite graph,Matching (graph theory),Assignment problem,3-dimensional matching,Time complexity,Blossom algorithm,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
97 | 5 | 0020-0190 |
Citations | PageRank | References |
2 | 0.45 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Morteza Fayyazi | 1 | 9 | 1.64 |
| David Kaeli | 2 | 1535 | 129.85 |
| Waleed Meleis | 3 | 157 | 18.29 |