Computer and Modernization ›› 2024, Vol. 0 ›› Issue (06): 59-63.doi: 10.3969/j.issn.1006-2475.2024.06.010
Previous Articles Next Articles
Online:
Published:
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:
TP301.6 
ZHU Lingheng1, 2, GU Danpeng1, 2, TANG Songqiang1, 2, CHEN Xiaoyong1, 2. Algorithm for Layered Bipartite Graph Maximum Matching Problem[J]. Computer and Modernization, 2024, 0(06): 59-63.
0 / / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.c-a-m.org.cn/EN/10.3969/j.issn.1006-2475.2024.06.010
http://www.c-a-m.org.cn/EN/Y2024/V0/I06/59
An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query