The nonapproximability of OBDD minimization

DOI10.1006/inco.2001.3076zbMath1009.68057OpenAlexW2025762151MaRDI QIDQ1854498

Detlef Sieling

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/acdcd4e112d68dea1aecf58c67a18173d7af7c57

Mathematics Subject Classification ID

Related Items (10)

The complexity of minimizing and learning OBDDs and FBDDs ⋮ Ordered binary decision diagrams and the Shannon effect ⋮ Weighted \(A^*\) search - unifying view and application ⋮ Linear temporal logic symbolic model checking ⋮ On the minimization of (complete) ordered binary decision diagrams ⋮ Symbolic graphs: Linear solutions to connectivity related problems ⋮ Minimization of decision trees is hard to approximate ⋮ Minimization problems for parity OBDDs ⋮ Representation of graphs by OBDDs ⋮ Optimal ordered binary decision diagrams for read-once formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Properties of complexity measures for PRAMs and WRAMs
• On the effect of local changes in the variable ordering of ordered decision diagrams
• Lower bounds for depth-restricted branching programs
• Optimization, approximation, and complexity classes
• Efficient algorithms for the transformation between different types of binary decision diagrams
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• Improving the variable ordering of OBDDs is NP-complete
• Branching Programs and Binary Decision Diagrams
• Variable orderings and the size of OBDDs for random partially symmetric Boolean functions
• On the complexity of constructing optimal ordered binary decision diagrams
• Finding the optimal variable ordering for binary decision diagrams

This page was built for publication: The nonapproximability of OBDD minimization