A perfect matching algorithm for sparse bipartite graphs

DOI10.1016/0166-218X(84)90026-XzbMATH Open0554.05053OpenAlexW2078902693MaRDI QIDQ759771FDOQ759771

Authors: Eugeniusz Toczyłowski 

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90026-x

Recommendations

• A simple matching algorithm for regular bipartite graphs.
• scientific article; zbMATH DE number 1104328
• Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs
• scientific article; zbMATH DE number 67678
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)

zbMATH Keywords

algorithmsperfect matchingblock triangularization of matrices

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem

Cited In (9)

• Improved induced matchings in sparse graphs
• A distributed-memory algorithm for computing a heavy-weight perfect matching on bipartite graphs
• Recognizing sparse perfect elimination bipartite graphs
• A Fast Perfect-Matching Algorithm in Random Graphs
• On algorithms for permuting large entries to the diagonal of a sparse matrix
• Making bipartite graphs DM-irreducible
• Title not available (Why is that?)
• A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
• An extendable stable matching algorithm of a kind of bipartite graph

This page was built for publication: A perfect matching algorithm for sparse bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q759771)