Fast exact minimization of BDDs
Fast exact minimization of BDDs
复制标题
BDD 的快速精确最小化
DOI：
10.1145/277044.277099
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Wolfgang Günther
中科院分区：
文献类型：
--
作者：
R. Drechsler;Nicole Drechsler;Wolfgang Günther
提出了一种求降阶二值决策图（bdd）最优变量排序的精确算法。该算法利用了VLSI设计中已知的下界技术。到目前为止，这种技术仅用于理论考虑，这里根据我们的目的加以调整。此外，该算法支持对称方面，并利用基于散列的数据结构。实验结果证明了该方法的有效性。我们成功地最小化了最多64个变量的加法器函数，而之前提出的所有其他方法都失败了。
We present a new exact algorithm for finding the optimal variable ordering for reduced ordered Binary Decision Diagrams (BDDs). The algorithm makes use of a lower bound technique known from VLSI design. Up to now this technique has been used only for theoretical considerations and if is adapted here for our purpose. Furthermore, the algorithm supports symmetry aspects and makes use of a hashing based data structure. Experimental results are given to demonstrate the efficiency of our approach. We succeeded in minimizing adder functions with up to 64 variables, while all other previously presented approaches fail.