Abstract. Given an integer weighted bipartite graph {G = (U ⊔ V, E), w : E → Z} we consider the problems of finding all the edges that occur in some minimum weight matching of maximum cardinality and enumerating all the minimum weight perfect matchings. Moreover, we construct a subgraph Gcs of G which depends on an ǫ-optimal solution of the dual linear program associated to the assignment problem on {G, w} that allows us to reduced this problems to their unweighed variants on Gcs. For instance, when G has a perfect matching and we have an ǫ-optimal solution of the dual linear program associated to the assignment problem on {G, w}, we solve the problem of finding all the edges that occur in some minimum weight perfect matching in linear time on the number of edges. Therefore, starting from scratch we get an algorithm that solves this problem in time O( √ nm log(nW )), where n = |U | ≥ |V |, m = |E|, and W = max{|w(e)| : e ∈ E}.
For bipartite graphs, Valencia and Vargas REF studied the weighted version of this problem that asks to find all edges belonging to some minimum weight perfect matching.
Optimum matchings in weighted bipartite graphs
ArXiv
ArXiv
Mathematics Computer Science