The nonapproximability of OBDD minimization
From MaRDI portal
Publication:1854498
DOI10.1006/INCO.2001.3076zbMath1009.68057OpenAlexW2025762151MaRDI QIDQ1854498
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
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
