| 最大b匹配的花算法 |
| |
| 引用本文： | 焦波,邱涤珊,马满好,凌云.最大b匹配的花算法[J].高等学校计算数学学报,2006,28(4):318-328. |
| |
| 作者姓名： | 焦波 邱涤珊 马满好 凌云 |
| |
| 作者单位： | 国防科技大学信息系统与管理学院指挥自动化系4室,长沙,410073 |
| |
| 摘 要： | 1引言b匹配问题是匹配问题的推广,它在国内研究较少,但在国外已有一定研究．文献3]给出了b匹配的应用实例,文献4]～6]给出了b匹配算法的研究成果,这些算法主要有两类:第一类为通过b匹配问题的线性规划模型求解,第二类为将b匹配问题转化为匹配问题求解．本文首次提出增广迹的概念,证明定理1M为G的最大b匹配(?)G中不存在M增广迹]的正确性,并仿照最大匹配的花算法设计最大b匹配的花算法,即直接对b匹配问题求解,避免将b匹配问题转化为匹配问题,这样就可以将各顶点b(vi)
|
| 关 键 词： | 匹配问题 匹配算法 研究成果 模型求解 线性规划 问题求解 问题转化 文献 |
| 收稿时间： | 11 11 2004 12:00AM |
| 修稿时间： | 2004-11-11 |
THE BLOSSOM ALGORITHM OF MAXIMUM b MATCHING |
| |
| Jiao Bo,Qiu Dishan,Ma Manhao,Ling Yun.THE BLOSSOM ALGORITHM OF MAXIMUM b MATCHING[J].Numerical Mathematics A Journal of Chinese Universities,2006,28(4):318-328. |
| |
| Authors: | Jiao Bo Qiu Dishan Ma Manhao Ling Yun |
| |
| Institution: | Department of Command Automatization, College of Information System and Management,National Univ.of Defense Technology, Changsha 410073 |
| |
| Abstract: | This work presents the blossom algorithm of maximum b matching which imitates the blossom algorithm of maximum matching. At first,an extending alternating network subprogram will be given,then the blossom algorithm of maximum b matching will select different methods based on three different outputs of the extending alternating network subprogram,finally the graph G will not have any M augmenting trail,at this time,M is a maximum b matching of graph G. At the end of this work, the complexity of algorithm will be given. |
| |
| Keywords: | b matching alternating network Hungarian network blossom algorithm complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
