Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs
From MaRDI portal
Algorithms are given for enumerating all perfect, maximum and maximal matchings in bipartite graphs \(G=(V,E)\). A matching \(M\subset V\) is (i) perfect if each vertex of \(V\) is incident to some edge of \(M\), (ii) a maximum matching if its cardinality is maximum over all matchings, and (iii) maximal if it is contained in no other matching. The running time of the algorithms is \(O(| V|)\) per matching plus a small overhead. For the entire collection see [Zbl 0879.00060].
Recommendations
Cited in
(39)- On the complexity of SNP block partitioning under the perfect phylogeny model
- Finding all the perfect matchings in bipartite graphs
- Number of maximum matchings of bipartite graphs with positive surplus
- A constraint logic programming approach for generating all perfect matchings
- Heuristic enhancements of the search for the generation of all perfect matchings
- The parameterized complexity of some minimum label problems
- Size versus truthfulness in the house allocation problem
- A fast algorithm to construct a representation for transversal matroids
- Solving matching problems efficiently in bipartite graphs
- scientific article; zbMATH DE number 5909229 (Why is no real title available?)
- Maximum matchings in bipartite graphs via strong spanning trees
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
- scientific article; zbMATH DE number 4051678 (Why is no real title available?)
- scientific article; zbMATH DE number 4068924 (Why is no real title available?)
- Enumerating perfect matchings in n-cubes
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- scientific article; zbMATH DE number 67678 (Why is no real title available?)
- Finding all minimum-cost perfect matchings in Bipartite graphs
- Finding all maximally-matchable edges in a bipartite graph
- Alternative algorithms for counting all matchings in graphs
- A fast algorithm for enumerating bipartite perfect matchings
- Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs
- Maximum matchings in scale-free networks with identical degree distribution
- An Efficient Algorithm for Enumerating Pseudo Cliques
- scientific article; zbMATH DE number 6299967 (Why is no real title available?)
- Algorithms – ESA 2004
- Fast enumeration algorithms for non-crossing geometric graphs
- Polynomial-delay and polynomial-space enumeration of large maximal matchings
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
- Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching
- Traversing combinatorial 0/1-polytopes via optimization
- Reconfiguring planar perfect matchings via bounded length alternating cycles
- Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond
- Graph matching based on similarities in structure and attributes
- The complexity of deciding quantifier-free definability for unary signatures
- Computational complexity and exact techniques for scheduling problems with job prohibitions
- A perfect matching algorithm for sparse bipartite graphs
- Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
This page was built for publication: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4370201)
