Optimizing the Variable Order

Before representing and manipulating switching functions in terms of OBDDs, an order on the set of variables has to be fixed. In the previous chapter, we have seen that the construction of the optimal variable order is a very critical venture — as it is related to exploding running times. A good order can lead to a very compact representation and hence to small running times, whereas a bad representation may exceed the physically ex-isting memory and hence causes the whole computation to abort. Even in the cases where bad variable orders do not cause a memory overflow, they lead to unacceptably large running times.