Boolean Mapping Algorithm Based on Perfect Matching of Bipartite Graph

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.