一种求解二部图最大匹配问题新算法及其应用
作者:

A New Algorithm and Application of Solving Maximum Matching Problem of Bipartite Graph
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [8]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    提出了解决二部图最大匹配问题的分层网络优化算法,并应用新算法对排课问题进行求解。定义了分层网络的概念及匹配的规则,结合广度优先搜索策略生成分层网络体系,然后按网络逆序找出最大匹配。实验表明,算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果,具备良好的性能。

    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.

    参考文献
    1 陈光喜,丁宣浩,古天龙.离散数学.北京:电子工业出版社,2008.
    2 Bruce L. Clarke. Stability analysis of a model reaction network using graph theory. Chemical Physics, 1974,60(4):1493-1501.
    3 Woess W. Random Walk sonInfinit Graphs and Groups. Cambridge Tractsin Math: Cambridge University Press, 2000: 35-36.
    4 杨胜超,张瑞军.基于二分图最优匹配算法的毕业论文选题 系统.计算机系统应用,2008,17(7):14-17.
    5 彭宇新, Ngo CW,肖建国.一种基于二分图最优匹配的镜头 检索方法.电子学报,2004,32(7):1135-1139.
    6 Golumbic MC. Algorithmic Graph Theory and the Perfect Graph. New York: Academic Press,1980.57-58.
    7 李洪波,翟金刚.二部图最大匹配的快速动态优化算法.鲁东 大学学报,2006,22(3):168-170.
    8 刘文斌,高琳,王淑栋,刘向荣,许进.最大匹配问题的DNA表 面计算模型.电子学报,2003,31(10):1496-1499.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

唐敏,关健,邓国强,王海刚.一种求解二部图最大匹配问题新算法及其应用.计算机系统应用,2012,21(3):72-75,28

复制
分享
文章指标
  • 点击次数:2468
  • 下载次数: 5312
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2011-06-20
  • 最后修改日期:2011-09-04
文章二维码
您是第12853530位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号