Name
Abstract | ||
|---|---|---|
We present a new parallel algorithm for computing a maximum cardinality matching in a bipartite graph suitable for distributed memory computers. The presented algorithm is based on the Push-Relabel algorithm which is known to be one of the fastest algorithms for the bipartite matching problem. Previous attempts at developing parallel implementations of it have focused on shared memory computers using only a limited number of processors. We first present a straightforward adaptation of these shared memory algorithms to distributed memory computers. However, this is not a viable approach as it requires too much communication. We then develop our new algorithm by modifying the previous approach through a sequence of steps with the main goal being to reduce the amount of communication and to increase load balance. The first goal is achieved by changing the algorithm so that many push and relabel operations can be performed locally between communication rounds and also by selecting augmenting paths that cross processor boundaries infrequently. To achieve good load balance, we limit the speed at which global relabelings traverse the graph. In several experiments on a large number of instances, we study weak and strong scalability of our algorithm using up to 128 processors. The algorithm can also be used to find @e-approximate matchings quickly. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.parco.2011.09.004 | Parallel Computing |
Keywords | Field | DocType |
fastest algorithm,bipartite graph,communication round,memory computer,bipartite matching problem,shared memory computer,new algorithm,push-relabel algorithm,new parallel algorithm,shared memory algorithm,parallel algorithms,matching,bipartite graphs | Shared memory,Computer science,Parallel algorithm,Parallel computing,Bipartite graph,Distributed memory,Hopcroft–Karp algorithm,Theoretical computer science,Assignment problem,3-dimensional matching,Scalability | Journal |
Volume | Issue | ISSN |
37 | 12 | 0167-8191 |
Citations | PageRank | References |
5 | 0.46 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Langguth | 1 | 85 | 12.71 |
| Md. Mostofa Ali Patwary | 2 | 335 | 17.49 |
| Fredrik Manne | 3 | 549 | 49.60 |