二部图最大权匹配的符号ADD算法  

An ADD-based Algorithm for Maximum Weight Matching in Bipartite Graphs

作　　者：姚家保[1] 古天龙[1] 徐周波[1] 

机构地区：[1]桂林电子工业学院计算机系,广西桂林541004

出　　处：《桂林电子工业学院学报》2005年第3期42-46,共5页Journal of Guilin Institute of Electronic Technology

基　　金：广西自然科学基金资助项目(0448072)

摘　　要：利用代数决策图ADD数据结构,在KM算法基础上,提出了一种二部图最大权匹配的符号ADD算法。该算法引入优先函数概念,将传统的匹配选择转化成布尔运算,"并行"地搜索匹配集合。实验结果表明:与传统算法相比,该算法可以改善问题的状态空间复杂度。<Abstrcat> Algebraic Decision Diagram is a new efficient approach to solve combinatorial optimization problems. In this paper, according to Kuhn-Munkres algorithm, the authors propose a symbolic algorithm based on ADD data structure for the maximum weight matching in bipartite graphs. By using symbolic manipulations, this algorithm introduces the priority function applied to a 'parallel' search for the set of matching. Compared with the traditional algorithms, the experimental results demonstrate that the algorithm can improve state space complexity of the problem.

关 键 词：二部图 最大权匹配 代数决策图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]