Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
From MaRDI portal
Publication:5929919
DOI10.1006/jcss.2000.1733zbMath0970.68041MaRDI 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
68P05: Data structures
Related Items
Unnamed Item, Exact OBDD Bounds for Some Fundamental Functions, On the OBDD representation of some graph classes, On the minimization of (complete) ordered binary decision diagrams, On the size of (generalized) OBDDs for threshold functions, Exact OBDD bounds for some fundamental functions, Better upper bounds on the QOBDD size of integer multiplication, A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm, On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
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