Finding all the perfect matchings in bipartite graphs
From MaRDI portal
Publication:1324433
DOI10.1016/0893-9659(94)90045-0zbMath0792.68129OpenAlexW2038646777MaRDI QIDQ1324433
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
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
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
