Finding all minimum-cost perfect matchings in Bipartite graphs

DOI10.1002/NET.3230220504MaRDI QIDQ4014612zbMATH OpenOpenAlexFDO

Authors Komei Fukuda, Tomomi Matsui

Publication date 13 October 1992

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230220504

zbMATH Keywords

Hungarian methodminimal-cost perfect matchingweighted bipartite graph

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Programming involving graphs or networks (90C35)

Recommendations

• Finding all the perfect matchings in bipartite graphs
• Optimum matchings in weighted bipartite graphs
• scientific article; zbMATH DE number 2081005
• scientific article; zbMATH DE number 1104328
• A faster algorithm for minimum-cost bipartite perfect matching in planar graphs

Cited in

(22)

• Finding all the perfect matchings in bipartite graphs
• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• Solving a combinatorial problem with network flows
• Finding all common bases in two matroids
• Heuristic enhancements of the search for the generation of all perfect matchings
• Two phase algorithms for the bi-objective assignment problem
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• An efficient approach for the rank aggregation problem
• Exact solution approaches for bilevel assignment problems
• scientific article; zbMATH DE number 4068924 (Why is no real title available?)
• scientific article; zbMATH DE number 1104328 (Why is no real title available?)
• scientific article; zbMATH DE number 2081005 (Why is no real title available?)
• A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
• An Efficient Algorithm for Enumerating Pseudo Cliques
• scientific article; zbMATH DE number 6299967 (Why is no real title available?)
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching
• Enumeration algorithm for the edge coloring problem on bipartite graphs
• Traversing combinatorial 0/1-polytopes via optimization
• Maximum-expectation matching under recourse
• Graph matching based on similarities in structure and attributes
• An efficient algorithm for solving pseudo clique enumeration problem

This page was built for publication: Finding all minimum-cost perfect matchings in Bipartite graphs

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