# Finding the Optimal Variable Ordering for Binary Decision Diagrams

@article{Friedman1987FindingTO, title={Finding the Optimal Variable Ordering for Binary Decision Diagrams}, author={Steven J. Friedman and Kenneth J. Supowit}, journal={24th ACM/IEEE Design Automation Conference}, year={1987}, pages={348-356} }

The ordered binary decision diagram is a canonical representation for Boolean functions, presented by Bryant as a compact representation for a broad class of interesting functions derived from circuits. However, the size of the diagram is very sensitive to the choice of ordering on the variables; hence for some applications, such as Differential Cascode Voltage Switch (DCVS) trees, it becomes extremely important to find the ordering leading to the most compact representation. We present an… Expand

#### Figures and Topics from this paper

#### 150 Citations

Variable ordering algorithms for ordered binary decision diagrams and their evaluation

- Mathematics, Computer Science
- IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
- 1993

The results of experiments in variable ordering using an experimentally practical algorithm are presented, which is basically a depth-first traversal through a circuit from the output to the inputs. Expand

Genetic Algorithms for the Variable Ordering Problem of Binary Decision Diagrams

- Computer Science
- FOGA
- 2005

A new crossover technique that turned out to be very useful in combination with sifting as hybridization technique is presented and a definition of a distance graph which can serve as formal framework for efficient schemes for the fitness evaluation is provided. Expand

An improved branch and bound algorithm for exact BDD minimization

- Mathematics, Computer Science
- IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
- 2003

This paper presents a new exact branch and bound technique for determining an optimal variable order that makes use of a combination of three bounds and, by this, avoids unnecessary computations. Expand

On variable ordering of binary decision diagrams for the application of multi-level logic synthesis

- Computer Science
- Proceedings of the European Conference on Design Automation.
- 1991

The authors present variable ordering methods of BDD based on cover patterns and selects most binate variables first, and the one for multi-level circuits is based on depth first traverse of circuits. Expand

Combination of lower bounds in exact BDD minimization

- Mathematics, Computer Science
- 2003 Design, Automation and Test in Europe Conference and Exhibition
- 2003

This paper presents a new exact branch & bound technique for determining an optimal variable order and makes use of a combination of three bounds and by this avoids unnecessary computations. Expand

On Variable Ordering of Ordered Functional Decision Diagrams

- 1994

In this paper methods for nding good variable orderings for ordered functional decision diagrams (OFDDs) are investigated. We present an algorithm for exact minimization of OFDDs that is applicable… Expand

Circuit width, register allocation, and ordered binary decision diagrams

- Mathematics, Computer Science
- IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
- 1991

The relationship between two important means of representing Boolean functions, combinational circuits and ordered binary decision diagrams (OBDDs), and algorithms for register allocation can be used to determine a good variable order for OBDD construction are studied. Expand

The Nonapproximability of OBDD Minimization

- Computer Science, Mathematics
- Inf. Comput.
- 2002

It is shown that, unless P=NP, for each constant c>1 there is no polynomial time approximation algorithm with the performance ratio c for the variable ordering problem, i.e., no polynnomial time algorithm that guarantees the computation of a variable ordering so that the resulting OBDD size is larger than the minimum size by a factor of at most c. Expand

Lower Bounds in Exact BDDMinimization

- Mathematics
- 2003

Ordered Binury Decision Diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequentl y use d in logic synthe sis and formal… Expand

Combining ordered best-first search with branch and bound for exact BDD minimization

- Mathematics
- 2005

Reduced-ordered binary decision diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis. The size of BDDs… Expand

#### References

SHOWING 1-10 OF 12 REFERENCES

Graph-Based Algorithms for Boolean Function Manipulation

- Computer Science
- IEEE Transactions on Computers
- 1986

Experimental results from applying a new data structure for representing Boolean functions and an associated set of manipulation algorithms to problems in logic design verification demonstrate the practicality of this approach. Expand

Functional Test Generation for Digital Circuits Described Using Binary Decision Diagrams

- Mathematics, Computer Science
- IEEE Transactions on Computers
- 1986

This correspondence presents a test generation methodology for VLSI circuits described at the functional level, which proposes a generalized D algorithm for generating tests to detect functional as well as gate-level faults. Expand

A New Method for Verifying Sequential Circuits

- Computer Science
- 23rd ACM/IEEE Design Automation Conference
- 1986

An algorithm for deciding whether two given synchronous, logic-level sequential circuits are functionally equivalent, as opposed to the (often very time-consuming) generation and simulation of numerous test vector sequences is presented. Expand

Decision Trees and Diagrams

- Computer Science
- CSUR
- 1982

In this tutorial survey a common framework of defimtmns and notation is established, the contributions from the main fields of apphcatmn are reviewed, recent results and extensions are presented, and areas of ongoing and future research are discussed. Expand

Symbolic Verification of MOS Circuits

- Computer Science
- 1985

The concept of symbolic simulation is presented, an algorithms for switch-level symbolic simulation are derived, and experimental measurements from MOSSYM are presented. Expand

ACORN: A Local Customization Approach to DCVS Physical Design

- Engineering
- DAC 1985
- 1985

Differential cascode voltage switch (DCVS) trees are high performance, high functionality CMOS circuits, which, because they have a large number of inputs and internal connections, are difficult to… Expand

ACORN: A Local Customization Approach to DCVS Physical Design

- Computer Science
- 22nd ACM/IEEE Design Automation Conference
- 1985

A DCVS customization procedure that exploits the fact that a Boolean function has more than one physical realization, and a group of three interconnected macros comprising approximately 800 DCVS trees are described. Expand

The Design and Analysis of Computer Algorithms

- Computer Science
- 1974

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs. Expand

Paper 2.

- Medicine
- The Australian journal of physiotherapy
- 1973

As with most rehabilitation programmes today, I believe that Cardiac Rehabilitation is best conducted as a team effort, each member making his own contribution, yet acting in a unified manner to… Expand

Construction of Optimal DCVS Trees

- Construction of Optimal DCVS Trees
- 1986