最大b匹配的花算法  

THE BLOSSOM ALGORITHM OF MAXIMUM b MATCHING

作　　者：焦波[1] 邱涤珊[1] 马满好[1] 凌云[1] 

机构地区：[1]国防科技大学信息系统与管理学院指挥自动化系4室,长沙410073

出　　处：《高等学校计算数学学报》2006年第4期318-328,共11页Numerical Mathematics A Journal of Chinese Universities

摘　　要：1引言 b匹配问题是匹配问题的推广，它在国内研究较少，但在国外已有一定研充文献[3]给出了b匹配的应用实例，文献[4]-[6]给出了b匹配算法的研究成果，这些算法主要有两类：第一类为通过b匹配问题的线性规划模型求解，第二类为将b匹配问题转化为匹配问题求解．本文首次提出增广迹的概念，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.

关 键 词：匹配问题 匹配算法 研究成果 模型求解 线性规划 问题求解 问题转化 文献 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]