Improving the variable ordering of OBDDs is NP-complete

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

On the effect of local changes in the variable ordering of ordered decision diagrams
On the Complexity of Some Ordering Problems
On the complexity of constructing optimal ordered binary decision diagrams
On the minimization of (complete) ordered binary decision diagrams
The nonapproximability of OBDD minimization

Cited in

(71)

On threshold BDDs and the optimal variable ordering problem
On the use of MTBDDs for performability analysis and verification of stochastic systems.
BDDs -- design, analysis, complexity, and applications.
Optimal ordered binary decision diagrams for read-once formulas
The complexity of minimizing and learning OBDDs and FBDDs
Weighted positive binary decision diagrams for exact probabilistic inference
Hardness of indentifying the minimum ordered binary decision diagram
The nonapproximability of OBDD minimization
On the use of binary decision diagrams for solving problems on simple games
Extending greedy feature selection algorithms to multiple solutions
A compositional approach to probabilistic knowledge compilation
The footprint form of a matrix: definition, properties, and an application
Compact representation of near-optimal integer programming solutions
Minimization problems for parity OBDDs
From MDD to BDD and arc consistency
Fault tree analysis: a survey of the state-of-the-art in modeling, analysis and tools
A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
Symbolic graphs: Linear solutions to connectivity related problems
On the influence of the variable ordering for algorithmic learning using OBDDs
Bounds on the OBDD-size of integer multiplication via universal hashing
On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
Factorization using binary decision diagrams
Exact stochastic constraint optimisation with applications in network analysis
Representing abstract dialectical frameworks with binary decision diagrams
Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
Solving quantified bit-vector formulas using binary decision diagrams
On application of multi-rooted binary decision diagrams to probabilistic model checking
Algebraic attacks using binary decision diagrams
Optimization Bounds from Binary Decision Diagrams
New hybrid genetic algorithm with adaptive operators and variability target for optimizing variable order in OBDD
Binary decision diagrams
Augmenting measure sensitivity to detect essential, dispensable and highly incompatible features in mass customization
Hierarchical Set Decision Diagrams and Automatic Saturation
On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
On Threshold BDDs and the Optimal Variable Ordering Problem
Quantum Differential Evolution Algorithm for Variable Ordering Problem of Binary Decision Diagram
An efficient relational deductive system for propositional non-classical logics
Characteristics of the maximal independent set ZDD
scientific article; zbMATH DE number 1222598 (Why is no real title available?)
scientific article; zbMATH DE number 1222599 (Why is no real title available?)
scientific article; zbMATH DE number 1222600 (Why is no real title available?)
On the Influence of the State Encoding on OBDD-Representations of Finite State Machines
On random orderings of variables for parity ordered binary decision diagrams
Optimizing probabilities in probabilistic logic programs
On the minimization of (complete) ordered binary decision diagrams
On the complexity of constructing optimal ordered binary decision diagrams
Modern Datalog Engines
Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
Finding small equivalent decision trees is hard
The Decomposition Tree for analyses of Boolean functions
Foundations of Genetic Algorithms
Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
String-matching with OBDDs
Quantum algorithm for finding the optimal variable ordering for binary decision diagrams
Learning ordered binary decision diagrams
A decision diagram operation for reachability
Lazy regular sensing
Automatically finding the right probabilities in Bayesian networks
Computing under-approximations of multivalued decision diagrams
Experimental and theoretical analysis of local search optimising OBDD variable orderings
On the effect of local changes in the variable ordering of ordered decision diagrams
INDIANA -- verifying (random) probing security through indistinguishability analysis
Explaining control policies through predicate decision diagrams
On reachability and controllability of switched Boolean control networks
A review of decision diagrams in system reliability modeling and analysis
Quantum algorithm for finding the optimal variable ordering for binary decision diagrams
Weighted A^* search - unifying view and application
Bandit-based Monte-Carlo structure learning of probabilistic logic programs
Forms of representation for simple games: sizes, conversions and equivalences
An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints

This page was built for publication: Improving the variable ordering of OBDDs is NP-complete

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