Minimizing the number of paths in BDDs: Theory and algorithm
Minimizing the number of paths in BDDs: Theory and algorithm
复制标题
最小化 BDD 中的路径数量：理论和算法
DOI：
--
复制
发表时间：
2006
影响因子：
2.9
通讯作者：
R. Drechsler
中科院分区：
文献类型：
--
作者：
G. Fey;R. Drechsler
电路和系统设计的复杂性迅速增加。因此，在电子设计自动化领域的研究的主要焦点是有效的算法和数据结构。其中，二元决策图（BDD）已被用于各种各样的应用，并从理论的角度进行了深入的研究。但大多数情况下，当考虑复杂性问题时，只分析了BDD中的节点数量。在这里，我们从理论和实践的角度来研究最小化BDD中的路径数。在计算机辅助设计的不同领域的连接概述，进行了理论研究，并提出了一种算法，以尽量减少路径的数量。实验结果表明了该算法的有效性。
The complexity of circuit and systems design increases rapidly. Therefore, a main focus of research in the area of electronic-design automation are efficient algorithms and data structures. Among these, binary decision diagrams (BDDs) have been used in a wide variety of applications and were intensively studied from a theoretical point of view. But mostly, when complexity issues were considered, only the number of nodes in a BDD has been analyzed. Here, we study minimizing the number of paths in BDDs from a theoretical and a practical point of view. Connections to different areas in computer-aided design are outlined, theoretical studies are carried out, and an algorithm to minimize the number of paths is presented. Experimental results show the efficiency of the algorithm.