摘要
提出了一种改进的基于二分图完美匹配的布尔匹配算法 .该算法通过把布尔变量之间的匹配问题转换为二分图的完美匹配问题 ,避免了原算法中因乘积项过多而导致计算时间过长的缺点 .对 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.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2001年第11期961-965,共5页
Journal of Computer-Aided Design & Computer Graphics
基金
美国国家科学基金 ( 5 978East Asia and Pacific Program -96 0 2 485 )资助