Dismiss
The InnovationQ application will be updated on Sunday, May 31st from 10am-noon ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

An Improvement to an Algorithm for Solving the Bipartite Weighted Matching

IP.com Disclosure Number: IPCOM000035192D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue

IBM

Related People

Authors:
Stone, HS [+details]

Abstract

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.