Abstract of Paper


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.