Parallel algorithms for bipartite matching problems on distributed memory computers

DOI10.1016/j.parco.2011.09.004zbMath1248.65145OpenAlexW2089353209MaRDI QIDQ712711

Fredrik Manne, Md. Mostofa Ali Patwary, Johannes Langguth

Publication date: 18 October 2012

Published in: Parallel Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.parco.2011.09.004

zbMATH Keywords

matchingparallel algorithmsbipartite graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel numerical computation (65Y05) Distributed systems (68M14)

Related Items (2)

A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs ⋮ State-of-the-Art Sparse Direct Solvers

Uses Software

• BSPlib
• SparseMatrix
• PSPIKE
• MC21A
• BSPedupack

Cites Work

• Unnamed Item
• Unnamed Item
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Clique partitions, graph compression and speeding-up algorithms
• Combinatorial optimization. Theory and applications.
• The university of Florida sparse matrix collection
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
• Heuristic initialization for bipartite matching problems
• Power balance and apportionment algorithms for the United States Congress
• Power balance and apportionment algorithms for the United States Congress
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Parallel algorithms for bipartite matching problems on distributed memory computers