AN EXTENSION OF THE BIPARTITE WEIGHTED MATCHING PROBLEM

Authors
HSIEH AJ HO CW FAN KC
Citation
Aj. Hsieh et al., AN EXTENSION OF THE BIPARTITE WEIGHTED MATCHING PROBLEM, Pattern recognition letters, 16(4), 1995, pp. 347-353
Citations number
10
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Artificial Intelligence
Journal title
Pattern recognition letters → ACNP
ISSN journal
01678655
Volume
16
Issue
4
Year of publication
1995
Pages
347 - 353
Database
ISI
SICI code
0167-8655(1995)16:4<347:AEOTBW>2.0.ZU;2-Z
Abstract
An extension of the bipartite weighted matching problem is considered in this paper. Given the weight of each edge and the penalty of each v ertex, the matching goal is to find a matching such that the sum of th e weights of matching edges plus the penalties of unmatched vertices i s minimum. In this paper, a reduction algorithm is proposed, which is found to be capable of reducing the matching problem to the assignment problem.