Algorithm for Layered Bipartite Graph Maximum Matching Problem
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 Algo-rithm 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.
layered bipartite graphmaximum matchingweighted maximum matchingpattern matchinggreedy strategy
国家科技期刊平台
NSTL
万方数据
