期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
