Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Sample Method for Minimization of OBDDs
| |
|
Sample Method for Minimization of OBDDs
Anna Slobodova5, 6  and Christoph Meinel7, 8
| (5) |
Compaq, Shrewsbury, Massachusets, USA |
| (6) |
Comenius University, Bratislava, Slovakia |
| (7) |
Institute of Telematics, Bahnhofstr 30-32, 54292 Trier, Germany |
| (8) |
FB IV - Informatik, University of Trier, 54286 Trier, Germany |
Abstract
The exact minimization of the size of Ordered Binary Decision Diagrams (OBDD) is known to be an NP-complete problem. The available
heuristical solutions of the problem still do not satisfy requirements of the practical applications. Development of the efficient
algorithms that find acceptable variable orders within a short time and with a modest memory overhead is hence higly desired.
In this paper we contribute to the solution of the minimization problem by a new variable reordering 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 extrapolated and applied to the entire OBDDs. We present the first experimental
results with the Sample Reordering targeted at combinatorial verification. The suggested heuristic is substantially faster
than Sifting.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|