Improving the variable ordering of OBDDs is NP-complete
Improving the variable ordering of OBDDs is NP-complete
复制标题
DOI：
10.1109/12.537122
复制
发表时间：
1996-09-01
影响因子：
3.7
通讯作者：
Wegener, I
中科院分区：
文献类型：
--
作者：
Bollig, B;Wegener, I
有序二元决策图是布尔函数的一种有用的表示，已知一种良好的变量排序。变量排序采用启发式算法计算，然后用局部搜索和模拟退火算法进行改进。这种方法是基于以下问题是NP完全的猜想。给定一个表示f的OBDD G和一个大小界s，是否存在一个表示至多s个节点的OBDD G*（关于任意变量排序）？证明了这一猜想。
Ordered binary decision diagrams are a useful representation of Boolean functions, ii a good variable ordering is known. Variable orderings are computed by heuristic algorithms and then improved with local search and simulated annealing algorithms. This approach is based on the conjecture that the following problem is NP-complete. Given an OBDD G representing f and a size bound s, does there exist an OBDD G* (respecting an arbitrary variable ordering) representing with at most s nodes? This conjecture is proved.