Finding all minimum-cost perfect matchings in Bipartite graphs

DOI10.1002/NET.3230220504zbMath0762.90080OpenAlexW1974151163MaRDI QIDQ4014612

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

weighted bipartite graphHungarian methodminimal-cost perfect matching

Mathematics Subject Classification ID

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

Related Items (14)

Exact solution approaches for bilevel assignment problems ⋮ An efficient algorithm for solving pseudo clique enumeration problem ⋮ Heuristic enhancements of the search for the generation of all perfect matchings ⋮ Polynomial-delay and polynomial-space enumeration of large maximal matchings ⋮ Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching ⋮ An Efficient Algorithm for Enumerating Pseudo Cliques ⋮ Two phase algorithms for the bi-objective assignment problem ⋮ Traversing combinatorial 0/1-polytopes via optimization ⋮ Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. ⋮ Solving a combinatorial problem with network flows ⋮ An efficient approach for the rank aggregation problem ⋮ Enumeration algorithm for the edge coloring problem on bipartite graphs ⋮ Finding all common bases in two matroids ⋮ Finding all the perfect matchings in bipartite graphs

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