Finding all the perfect matchings in bipartite graphs

DOI10.1016/0893-9659(94)90045-0zbMath0792.68129OpenAlexW2038646777MaRDI QIDQ1324433

V. Pereyra

Publication date: 23 June 1994

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

Full work available at URL: https://doi.org/10.1016/0893-9659(94)90045-0

zbMATH Keywords

bipartite graphperfect matchings

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)

Related Items (19)

Optimum matchings in weighted bipartite graphs ⋮ The structure of stable marriage with indifference ⋮ Algorithms for finding a \(K\)th best valued assignment ⋮ Regularization of DAEs based on the signature method ⋮ Multiconsistency and robustness with global constraints ⋮ Mining preserving structures in a graph sequence ⋮ Heuristic enhancements of the search for the generation of all perfect matchings ⋮ Enumerating perfect matchings in \(n\)-cubes ⋮ Perfect matching in bipartite hypergraphs subject to a demand graph ⋮ Finding all maximally-matchable edges in a bipartite graph ⋮ Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. ⋮ Solving a combinatorial problem with network flows ⋮ Small Littlewood-Richardson coefficients ⋮ The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable ⋮ A catalog of minimally nonideal matrices ⋮ A constraint logic programming approach for generating all perfect matchings ⋮ A fast algorithm to construct a representation for transversal matroids

Cites Work

• Algorithms for finding k-best perfect matchings
• The Complexity of Enumeration and Reliability Problems
• Finding all minimum-cost perfect matchings in Bipartite graphs
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Depth-First Search and Linear Graph Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Finding all the perfect matchings in bipartite graphs