Blockwise variable orderings for shared BDDs (extended abstract)
A common data structure for the representation of Boolean functions are ordered binary decision diagrams (OBDDs). The size of an OBDD representing a Boolean function depends on the variable ordering. Finding a variable ordering with optimal (i.e. minimum) OBDD size is a central, but NP-hard problem. It is of great interset to characterize optimal variable orderings from the structure of the given function. In this paper the problem of characterizing optimal variable orderings for shared OBDDs of two Boolean functions is investigated. In a special case tree-like circuits provide an example for such functions. Saeurhoff, Wegener and Werchner proved that there is some optimal ordering where all \(x\)-variables are tested before all \(y\)-variables or vice versa (blockwise variable ordering). In this paper, this special case is generalized. For the entire collection see [Zbl 0895.00049].
- Optimal ordered binary decision diagrams for read-once formulas
- Variable orderings and the size of OBDDs for random partially symmetric Boolean functions
- Improving the variable ordering of OBDDs is NP-complete
- On the effect of local changes in the variable ordering of ordered decision diagrams
- On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
- On threshold BDDs and the optimal variable ordering problem
- Optimal ordered binary decision diagrams for read-once formulas
- On the structure of counterexamples to symmetric orderings for BDD's
- Variable orderings and the size of OBDDs for random partially symmetric Boolean functions
- On the effect of local changes in the variable ordering of ordered decision diagrams
This page was built for publication: Blockwise variable orderings for shared BDDs (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218141)
