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

DOI10.1006/jcss.2000.1733zbMath0970.68041MaRDI 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

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