Title :
A note on complexity of OBDD composition and efficiency of partitioned-OBDDs over OBDDs
Author :
Jain, Jawahar ; Wegener, Ingo ; Fujita, Masahiro
Author_Institution :
Fujitsu Labs of America, Sunnyvale, CA, USA
fDate :
11/1/2001 12:00:00 AM
Abstract :
We discuss an open problem with constructing an OBDD using composition and prove that the worst case complexity of the construction is truly cubic. Using this insight, we show compactness of partitioned-OBDD over monolithic OBDD
Keywords :
Boolean functions; VLSI; binary decision diagrams; logic CAD; OBDD composition; compactness; cubic complexity; monolithic OBDD; partitioned-OBDD; worst case complexity; Binary decision diagrams; Boolean functions; Circuits; Computer science; Input variables; Phased arrays; Upper bound;
Journal_Title :
Computers, IEEE Transactions on
