The complexity of minimizing and learning OBDDs and FBDDs

DOI10.1016/S0166-218X(01)00324-9zbMath1002.68032MaRDI QIDQ1613429

Detlef Sieling

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

ordered binary decision diagramsfree binary decision diagrams

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

MCSP is hard for read-once nondeterministic branching programs, Minimization of decision trees is hard to approximate, Minimization problems for parity OBDDs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph driven BDDs -- a new data structure for Boolean functions
• Optimization, approximation, and complexity classes
• Hardness of indentifying the minimum ordered binary decision diagram
• The nonapproximability of OBDD minimization
• A theory of the learnable
• Graph-Based Algorithms for Boolean Function Manipulation
• On the complexity of branching programs and decision trees for clique functions
• Computational limitations on learning from examples
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• Improving the variable ordering of OBDDs is NP-complete
• On the complexity of constructing optimal ordered binary decision diagrams
• Finding the optimal variable ordering for binary decision diagrams