Incremental reduction of binary decision diagrams

A new method is presented to reduce the number of nodes of a binary decision diagram (BDD) after its construction, which the authors call incremental reduction. It is based on an algorithm that swaps two adjacent variables in the BDD ordering. The initial ordering is obtained by an algorithm. Experiments have shown that an average reduction of 20% on the number of nodes of these initial BDDs can be achieved with the authors' method.