The Complexity of the Optimal Variable Ordering Problems of Shared Binary Decision Diagrams
The Complexity of the Optimal Variable Ordering Problems of Shared Binary Decision Diagrams
复制标题
共享二元决策图最优变量排序问题的复杂性
DOI：
10.1007/3-540-57568-5_270
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
S. Yajima
中科院分区：
文献类型：
--
作者：
S. Tani;K. Hamaguchi;S. Yajima
二进制决策图（BDD）是表示布尔函数的有向无环图。BDD被广泛应用于各种需要布尔函数操作的领域，因为BDD可以有效地表示许多实际的布尔函数并具有其他理想的属性。然而，构建BDD的复杂性在理论上鲜有研究。本文证明了共享BDD的最优变量排序问题是np完全的，并讨论了该问题和BDD的相关问题的硬度。
A binary decision diagram (BDD) is a directed acyclic graph for representing a Boolean function. BDD's are widely used in various areas which require Boolean function manipulation, since BDD's can represent efficiently many of practical Boolean functions and have other desirable properties. However the complexity of constructing BDD's has hardly been researched theoretically. In this paper, we prove that the optimal variable ordering problem of shared BDD's is NP-complete, and touch on the hardness of this problem and related problems of BDD's.