Efficient breadth-first manipulation of binary decision diagrams
Pranav N Ashar, Matthew Cheong · 1994
We propose new techniques for efficient breadth-first iterative ma-nipulation of ROBDDs. Breadth-first iterative ROBDD manipula-tion can potentially reduce the total elapsed time by multiple orders of magnitude compared to the conventional depth-first recursive al-gorithms when the memory requirement exceeds the available phys-ical memory. However, the breadth-first manipulation algorithms proposed so far [5] have had a large enough overhead associated with them to make them impractical. Our techniques are geared towards minimizing the overhead without sacrificing the speed up potential. Experimental results indicate considerable success in that regard.