A perfect matching algorithm for sparse bipartite graphs

DOI10.1016/0166-218X(84)90026-XMaRDI QIDQ759771zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmsblock triangularization of matricesperfect matching

Mathematics Subject Classification ID

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

Review text

The algorithms for finding a perfect matching, if any, in a bipartite undirected graph G usually start with a matching (which may not be maximum) and construct, if it exists, a matching of greater cardinality by determining augmenting paths. This is generally obtained through an associated directed graph \(\bar G.\) The paper shows that those edges of \(\bar G\) which link vertices belonging to different strongly connected components should not be included in augmenting paths. An application to the block triangularization of very large, sparse, nonsingular matrices is given.

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})\)

Cites work

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

Cited in

(11)

• Finding all the perfect matchings in bipartite graphs
• On algorithms for permuting large entries to the diagonal of a sparse matrix
• Recognizing sparse perfect elimination bipartite graphs
• A Fast Perfect-Matching Algorithm in Random Graphs
• scientific article; zbMATH DE number 67678 (Why is no real title available?)
• Making bipartite graphs DM-irreducible
• A Competitive Strong Spanning Tree Algorithm for the Maximum Bipartite Matching Problem
• An extendable stable matching algorithm of a kind of bipartite graph
• A distributed-memory algorithm for computing a heavy-weight perfect matching on bipartite graphs
• A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
• Improved induced matchings in sparse graphs

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)