US5841958A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Bipartite matching
Assignee: NEC Corp
•
Filing: 1995-01-19
•
Granted: 1998-11-24
•
Expires: 2015-01-19
Abstract
Abstract A computer technique for bipartite matching of objects of one subset with objects of a different subset where multiple choices are permitted. A bipartite graph is formed in which the objects form nodes and the edges connecting pairs of nodes represent costs of matching the nodes connected. The original tour or graph is decomposed into a plurality of quasi-convex subtours or subgraphs and the minimum cost match of each subtour is found and the union of all such matches of the subtours is used as the desired match.
Inventors
- 👤 Samuel R. Buss
- 👤 Peter N. Yianilos
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 14:35
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/26; G06V; G06V30/00; G06V30/10; G06V30/19; G06V30/196; G06V30/1983; G06V30/1988
Claims Analysis
Total Claims: 5
Claim 1
Independent Claim
146 words
A process for performing bipartite matching of an object of a first subset with an object of a second subset comprising the steps of: preparing a graph as a tour in which the objects of the first and second subsets form the nodes and the distance between an object of the first subset and an object of the second subset is the cost of the bipartite matching of such two objects, decomposing the tour to form an interleaved set of quasi-convex subtours in each of which the nodes alternate between the first and second subsets, whereby the decomposition is such that a union of the minimum cost match for this set of subtours will be a minimum cost-match of the tour, finding the minimum cost-match of each subtour, and combining all the minimum cost-matches to form the desired bipartite match of the objects to be matched.
Claim 2
Dependent Claim
146 words
A process for performing bipartite matching of an object of a first subset with an object of a second subset comprising the steps of: preparing a graph as a tour in which the objects of the first and second subsets form the nodes and the distance between an object of the first subset and an object of the second subset is the cost of the bipartite matching of such two objects, decomposing the tour to form an interleaved set of quasi-convex subtours in each of which the nodes alternate between the first and second subsets, whereby the decomposition is such that a union of the minimum cost match for this set of subtours will be a minimum cost-match of the tour, finding the minimum cost-match of each subtour, and combining all the minimum cost-matches to form the desired bipartite match of the objects to be matched.
Claim 3
Dependent Claim
45 words
A computer that includes a storage medium in which there is included a program for operating the computer in accordance with the process of claim 1 when the computer is supplied with the two subsets between which the desired bipartite matching is to be made.
Claim 4
Dependent Claim
35 words
A process in accordance with claim 1 in which the objects of the first subset and second subsets are strings of characters and the bipartite match will be a pair of matching strings of characters.
Claim 5
Dependent Claim
61 words
The process of claim 1 in which the step of finding the minimum cost match of each subtour comprises the steps of searching iteratively for jumpers that qualify as minimal candidates, matching nearest neighbor pairs included within minimal candidate pairs, and recursively applying the last-mentioned searching and matching steps to the remainder of the subtour until all the nodes are paired.
References Cited (Backward Citations)
US5481668A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-23 | 2002-05-25 | 2002-11-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-23 | 2006-05-25 | 2006-11-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-23 | 2010-05-25 | 2010-11-24 | $7700.00 | Window Closed / Lapsed |