Sample Method for Minimization of OBDDs
by Anna Slobodova, Christoph Meinel
Abstract:
This paper contributes to the solution of the minimization problem of Ordered Binary Decision Diagrams by means of variable reordering. We suggest a new heuristic that is based on sampling. A small OBDD sample is chosen from the OBDDs that are considered for minimization. Solving the problem for this small sample, we obtain a variable order that is adapt for the entire OBDDs. We present first experimental results with the Sample Reordering targeted at combinatorial verification. The suggested heuristic is substantially faster than Sifting.