The nonapproximability of OBDD minimization

DOI10.1006/INCO.2001.3076MaRDI QIDQ1854498zbMATH OpenOpenAlexFDO

Authors 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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Improving the variable ordering of OBDDs is NP-complete
• On the hardness of approximating the minimum consistent OBDD problem
• The complexity of minimizing and learning OBDDs and FBDDs
• On the minimization of (complete) ordered binary decision diagrams
• On the Width of Ordered Binary Decision Diagrams

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1354131 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Branching Programs and Binary Decision Diagrams
• Efficient algorithms for the transformation between different types of binary decision diagrams
• Finding the optimal variable ordering for binary decision diagrams
• Graph-Based Algorithms for Boolean Function Manipulation
• Improving the variable ordering of OBDDs is NP-complete
• Lower bounds for depth-restricted branching programs
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the complexity of constructing optimal ordered binary decision diagrams
• On the effect of local changes in the variable ordering of ordered decision diagrams
• Optimization, approximation, and complexity classes
• Properties of complexity measures for PRAMs and WRAMs
• Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

Cited in

(16)

• The complexity of minimizing and learning OBDDs and FBDDs
• Ordered binary decision diagrams and the Shannon effect
• Weighted \(A^*\) search - unifying view and application
• Optimal ordered binary decision diagrams for read-once formulas
• Improving the variable ordering of OBDDs is NP-complete
• On the hardness of approximating the minimum consistent OBDD problem
• Output-size sensitiveness of OBDD construction through maximal independent set problem
• Nondeterministic unitary OBDDs
• Minimization of decision trees is hard to approximate
• Linear temporal logic symbolic model checking
• Minimization problems for parity OBDDs
• Representation of graphs by OBDDs
• Introduction to the OBDD algorithm for the ATP community
• On the minimization of (complete) ordered binary decision diagrams
• Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard
• Symbolic graphs: Linear solutions to connectivity related problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854498)