An extension of the bipartite weighted matching problem

Ai Jia Hsieh, Chin Wen Ho, Kuo Chin Fan

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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 vertex, the matching goal is to find a matching such that the sum of the weights of matching edges plus the penalties of unmatched vertices is minimum. In this paper, a reduction algorithm is proposed, which is found to be capable of reducing the matching problem to the assignment problem.

Original languageEnglish
Pages (from-to)347-353
Number of pages7
JournalPattern Recognition Letters
Volume16
Issue number4
DOIs
StatePublished - Apr 1995

Keywords

  • Assignment problem
  • Bipartite weighted matching
  • Hungarian method

Cite this