计算机与现代化Issue(6)：59-63,102,6.DOI:10.3969/j.issn.1006-2475.2024.06.010
一种多层级二分图最大匹配问题的快速算法
Algorithm for Layered Bipartite Graph Maximum Matching Problem
摘要
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 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.关键词
二分图/最大匹配/最大权匹配/模式匹配/贪心策略Key words
layered bipartite graph/maximum matching/weighted maximum matching/pattern matching/greedy strategy分类
信息技术与安全科学引用本文复制引用
主令恒,顾丹鹏,唐松强,陈肖勇..一种多层级二分图最大匹配问题的快速算法[J].计算机与现代化,2024,(6):59-63,102,6.基金项目
国家重点研发计划项目(2022YFB2602101) （2022YFB2602101）
