ON THE EFFECT OF LOCAL CHANGES IN THE VARIABLE ORDERING OF ORDERED DECISION DIAGRAMS

Ordered binary and functional decision diagrams (OBDDs and OFDDs) have turned out to be useful representations of Boolean functions with man y applications. Since it is NP-hard to compute an optimal variable ord ering or to improve a given variable ordering, local search and simula ted annealing algorithms are used to improve variable orderings. The e ffect of local changes in variable orderings is studied and a simulate d annealing algorithm for the computation of good variable orderings i s presented. For several benchmark circuits the best known variable or derings are improved significantly.