Computer and Modernization ›› 2024, Vol. 0 ›› Issue (06): 59-63.doi: 10.3969/j.issn.1006-2475.2024.06.010

Previous Articles     Next Articles

Algorithm for Layered Bipartite Graph Maximum Matching Problem

  



  1. (1. PowerChina Huadong Engineering Corporation Limited, Hangzhou, 310000 China;
    2. Zhejiang Huadong Engineering Digital Technology Co. Ltd, Hangzhou, 310000 China)
  • Online:2024-06-30 Published:2024-07-17

Abstract: Abstract: This paper brought up a new problem model for bipartite match problem. In this problem, the entities to be matched contains sub-entities which are also to be matched. That is, the entities to be matched has father-son relations. This model can be applied to many situation, like database schema match, and team match. This paper gave a polynomial-time algorithm, the idea of which is to break down this problem into a combination of Bipartite Graph Maximum Matching Problem and Weighted Maximum Matching Problem. There are mature algorithms (Hungarian Algorithm and Kuhn-Munkres Algorithm) that can solve these two classic problems. The process of the combination takes a kind of greedy strategy. Among sub-entities, Hungarian Algorithm is applied. After that, we take the matching results as the weights and apply Kuhn-Munkres Algorithm among super-entities, and then we get the final result. This paper also proved the correctness of this algorithm, and analyzed its performance through experiments.

Key words: Key words: layered bipartite graph, maximum matching, weighted maximum matching, pattern matching, greedy strategy

CLC Number: