Computer Science Department
School of Computer Science, Carnegie Mellon University


Breadth-First with Depth-First BDD Construction: A Hybrid Approach

Yirng-An Chen, Bwolen Yang, Randal E. Bryant

March 1997

Keywords: Breadth-first, depth-first, hybrid approach, binary decision diagram, formal verification

This paper presents the technique of operator sifting as a new way of understanding both breadth-first and depth-first approaches to BDD construction. A new algorithm is also proposed to capture the breadth-first approach's advantage of memory access locality, while keeping the depth-first approach's advantage of low memory overhead. Our preliminary experimental results show that our approach is generally faster than other implementations that rely exclusively on either breadth-first or depth-first approaches while keeping memory overhead comparable to that of depth-first approaches.

18 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by