On the OBDD-representation of general Boolean functions
Heh-Tyan Liaw, Chen-Shang Lin · IEEE Transactions on Computers · 1992
The behavior of ordered binary decision diagrams (OBDD) for general Boolean functions is studied. A tight upper bound of (2/sup n//n)(2+ epsilon ) for the worst case OBDD size is derived. Although the size of an OBDD is dependent on the ordering of decision variables, it is shown that almost all functions are not sensitive to variable ordering.>