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

作者简介:

通讯作者:

中图分类号:

基金项目:


A New Algorithm and Application of Solving Maximum Matching Problem of Bipartite Graph
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 增强出版
  • |
  • 文章评论
    摘要:

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

    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

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

京公网安备 11040202500063号