A note on complexity of OBDD composition and efficiency of partitioned-OBDDs over OBDDs
Jawahar Jain, Ingo Wegener, Masahiro Fujita · IEEE Transactions on Computers · 2001
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.