Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-022 | 15th March 1996 00:00

Optimal Ordered Binary Decision Diagrams for Tree-like Circuits



Many Boolean functions have short representations by OBDDs (ordered
binary decision diagrams) if appropriate variable orderings are used.
For tree-like circuits, which may contain EXOR-gates, it is proved
that some depth first traversal leads to an optimal variable ordering.
Moreover, an optimal variable ordering and the resulting OBDD
can be computed in time linear in the number of variables and the size of
the OBDD, respectively.
Upper and lower bounds on the OBDD size of the functions
representable by tree-like circuits are derived.
For, e. g., 1024 inputs, we show that all tree-like circuits have
OBDDs of size at 5349 and we give an example of a tree-like circuit
requiring an OBDD of size 5152.

ISSN 1433-8092 | Imprint