本文已被：浏览 2286次 下载 5042次
Received:June 20, 2011 Revised:September 04, 2011
Received:June 20, 2011 Revised:September 04, 2011
中文摘要: 提出了解决二部图最大匹配问题的分层网络优化算法,并应用新算法对排课问题进行求解。定义了分层网络的概念及匹配的规则,结合广度优先搜索策略生成分层网络体系,然后按网络逆序找出最大匹配。实验表明,算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果,具备良好的性能。
Abstract:This paper proposed an algorithm for maximum matching of Bipartite graph based on layered network model. Timetable Problems are solved by the new algorithm. A matching rule for layered networks is defined and proposed a concept of layered network first, and a layered network system is generated with the breadth first search strategy. Maximal matching is found according reversed network order. Experiments show that this algorithm can get accurate results and has a good performance with computational complexity in solving large-scale theoretical and practical maximum matching problems of bipartite graph.
文章编号： 中图分类号： 文献标志码：
基金项目:
引用文本：
唐敏,关健,邓国强,王海刚.一种求解二部图最大匹配问题新算法及其应用.计算机系统应用,2012,21(3):72-75,28
TANG Min,GUAN Jiang,DENG Guo-Qiang,WANG Hai-Gang.A New Algorithm and Application of Solving Maximum Matching Problem of Bipartite Graph.COMPUTER SYSTEMS APPLICATIONS,2012,21(3):72-75,28
唐敏,关健,邓国强,王海刚.一种求解二部图最大匹配问题新算法及其应用.计算机系统应用,2012,21(3):72-75,28
TANG Min,GUAN Jiang,DENG Guo-Qiang,WANG Hai-Gang.A New Algorithm and Application of Solving Maximum Matching Problem of Bipartite Graph.COMPUTER SYSTEMS APPLICATIONS,2012,21(3):72-75,28
