Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems

DOI10.1006/jcss.2000.1733zbMath0970.68041OpenAlexW2073480341MaRDI QIDQ5929919

Ingo Wegener, Beate Bollig

Publication date: 17 April 2001

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1733

zbMATH Keywords

ordered binary decision diagrams

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Better upper bounds on the QOBDD size of integer multiplication ⋮ On the OBDD representation of some graph classes ⋮ Exact OBDD bounds for some fundamental functions ⋮ A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm ⋮ On the minimization of (complete) ordered binary decision diagrams ⋮ On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem ⋮ On the size of (generalized) OBDDs for threshold functions ⋮ Unnamed Item ⋮ Exact OBDD Bounds for Some Fundamental Functions

Cites Work

• Unnamed Item
• Unnamed Item
• Worst case examples for operations on OBDDs
• On the effect of local changes in the variable ordering of ordered decision diagrams
• Neither reading few bits twice nor reading illegally helps much
• Reduction of OBDDs in linear time
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• A note on read-$k$ times branching programs
• Improving the variable ordering of OBDDs is NP-complete
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• On a problem of K. Zarankiewicz