Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TREE-LIKE CIRCUIT:
Reports tagged with Tree-like Circuit:
TR96-022 | 15th March 1996
Martin Sauerhoff, Ingo Wegener, Ralph Werchner

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 ... more >>>




ISSN 1433-8092 | Imprint