Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
From MaRDI portal
Publication:5929919
DOI10.1006/jcss.2000.1733zbMath0970.68041OpenAlexW2073480341MaRDI QIDQ5929919
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
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