Name
Title | ||
|---|---|---|
A matrix-algebraic formulation of distributed-memory maximal cardinality matching algorithms in bipartite graphs. |
Abstract | ||
|---|---|---|
We describe parallel algorithms for computing maximal cardinality matching in a bipartite graph on distributed-memory systems. Unlike traditional algorithms that match one vertex at a time, our algorithms process many unmatched vertices simultaneously using a matrix-algebraic formulation of maximal matching. This generic matrix-algebraic framework is used to develop three efficient maximal matching algorithms with minimal changes. The newly developed algorithms have two benefits over existing graph-based algorithms. First, unlike existing parallel algorithms, cardinality of matching obtained by the new algorithms stays constant with increasing processor counts, which is important for predictable and reproducible performance. Second, relying on bulk-synchronous matrix operations, these algorithms expose a higher degree of parallelism on distributed-memory platforms than existing graph-based algorithms. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.parco.2016.05.007 | Parallel Computing |
Keywords | Field | DocType |
cardinality matching,bipartite graph,parallel algorithm,matrix-algebra | Analysis of parallel algorithms,Computer science,Bipartite graph,Parallel computing,Algorithm,Probabilistic analysis of algorithms,Matching (graph theory),Hopcroft–Karp algorithm,Theoretical computer science,Factor-critical graph,3-dimensional matching,Blossom algorithm | Journal |
Volume | Issue | ISSN |
58 | C | 0167-8191 |
Citations | PageRank | References |
1 | 0.37 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ariful Azad | 1 | 138 | 15.71 |
| Aydin Buluc | 2 | 1057 | 67.49 |