An Improvement to an Algorithm for Solving the Bipartite Weighted Matching
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28
This article describes an improvement to an algorithm for solving the bipartite weighted-matching problem. The bipartite weighted-matching problem is a problem in which there is a bipartite graph with N source nodes, N sink nodes, and edges (i, j) where i is a source node and j is a sink node. Each edge carries a weight wt(i, j). The objective is to find a maximal matching of minimum weight. A matching is a subset of edges with the property that no sink or source node touches more than one edge in the matching. A maximal matching is a matching that contains as many edges as possible.