关键词: 关键词：二分图, 最大匹配, 最大权匹配, 模式匹配, 贪心策略

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