A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs

DOI10.1137/18M1189348zbMath1451.05189arXiv1801.09809OpenAlexW3098045814WikidataQ114978700 ScholiaQ114978700MaRDI QIDQ5132024

No author found.

Publication date: 9 November 2020

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.09809

zbMATH Keywords

matchingtransversalsparallel algorithmsbipartite graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Transversal (matching) theory (05D15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (4)

A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs ⋮ Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations

Uses Software

• SuperLU-DIST
• SparseMatrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Push-relabel based algorithms for the maximum transversal problem
• Parallel algorithms for bipartite matching problems on distributed memory computers
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• A generic auction algorithm for the minimum cost network flow problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A new pivoting strategy for Gaussian elimination
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix
• The university of Florida sparse matrix collection
• Design, implementation, and analysis of maximum transversal algorithms
• Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
• On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices
• A new approach to the maximum-flow problem
• Computing the block triangular form of a sparse matrix
• Scaling Algorithms for Weighted Matching in General Graphs
• Sparse Matrix Computations on Parallel Processor Arrays
• Heuristic initialization for bipartite matching problems
• SuperLU_DIST
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs