基于二分图完美匹配的布尔匹配算法

Boolean Mapping Algorithm Based on Perfect Matching of Bipartite Graph

提出了一种改进的基于二分图完美匹配的布尔匹配算法 .该算法通过把布尔变量之间的匹配问题转换为二分图的完美匹配问题 ,避免了原算法中因乘积项过多而导致计算时间过长的缺点 .对 MCNC标准测试电路的实验结果表明 :与原算法相比 ,改进后的算法可以减少 2 1%左右的计算时间 .同时 ,文中提出了布尔变量强匹配的概念 ,它是对传统布尔匹配概念的引申 .

An improved Boolean matching algorithm based on transforming the mapping between Boolean variables into the problem of perfect matching of bipartite graph is presented. This approach can overcome the shortcoming of the original algorithm, i.e., lengthy computation time caused by the excessive product terms. Experiments on MCNC benchmarks show that the improved approach can reduce computation time by about 21% compared to the original algorithm. Also, the concept of strong matching between Boolean variables is put forward as the generalization of conventional Boolean variable mapping.