Improving the variable ordering of OBDDs is NP-complete
From MaRDI portal
Publication:4420841
DOI10.1109/12.537122zbMath1048.68571OpenAlexW2141472133WikidataQ56340203 ScholiaQ56340203MaRDI QIDQ4420841
Publication date: 1996
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/12.537122
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (54)
The complexity of minimizing and learning OBDDs and FBDDs ⋮ On the Influence of the State Encoding on OBDD-Representations of Finite State Machines ⋮ On Application of Multi-Rooted Binary Decision Diagrams to Probabilistic Model Checking ⋮ Weighted \(A^*\) search - unifying view and application ⋮ Binary Decision Diagrams ⋮ Factorization using binary decision diagrams ⋮ Augmenting measure sensitivity to detect essential, dispensable and highly incompatible features in mass customization ⋮ The footprint form of a matrix: definition, properties, and an application ⋮ String-matching with OBDDs ⋮ Exact stochastic constraint optimisation with applications in network analysis ⋮ Weighted positive binary decision diagrams for exact probabilistic inference ⋮ On the use of binary decision diagrams for solving problems on simple games ⋮ Algebraic Attacks Using Binary Decision Diagrams ⋮ Modern Datalog Engines ⋮ Characteristics of the maximal independent set ZDD ⋮ Learning ordered binary decision diagrams ⋮ Bandit-based Monte-Carlo structure learning of probabilistic logic programs ⋮ Decision Diagrams for Discrete Optimization: A Survey of Recent Advances ⋮ Compact representation of near-optimal integer programming solutions ⋮ On the use of MTBDDs for performability analysis and verification of stochastic systems. ⋮ A decision diagram operation for reachability ⋮ Forms of representation for simple games: sizes, conversions and equivalences ⋮ Hierarchical Set Decision Diagrams and Automatic Saturation ⋮ Optimization Bounds from Binary Decision Diagrams ⋮ Representing abstract dialectical frameworks with binary decision diagrams ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ On the effect of local changes in the variable ordering of ordered decision diagrams ⋮ On the minimization of (complete) ordered binary decision diagrams ⋮ Symbolic graphs: Linear solutions to connectivity related problems ⋮ On random orderings of variables for parity ordered binary decision diagrams ⋮ Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems ⋮ On reachability and controllability of switched Boolean control networks ⋮ An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints ⋮ Minimization problems for parity OBDDs ⋮ Lazy regular sensing ⋮ On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem ⋮ Extending greedy feature selection algorithms to multiple solutions ⋮ The Decomposition Tree for analyses of Boolean functions ⋮ Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams ⋮ Quantum Differential Evolution Algorithm for Variable Ordering Problem of Binary Decision Diagram ⋮ On threshold BDDs and the optimal variable ordering problem ⋮ Solving Quantified Bit-Vector Formulas Using Binary Decision Diagrams ⋮ A compositional approach to probabilistic knowledge compilation ⋮ An efficient relational deductive system for propositional non-classical logics ⋮ Optimal ordered binary decision diagrams for read-once formulas ⋮ From MDD to BDD and arc consistency ⋮ On the influence of the variable ordering for algorithmic learning using OBDDs ⋮ Hardness of indentifying the minimum ordered binary decision diagram ⋮ FINDING SMALL EQUIVALENT DECISION TREES IS HARD ⋮ Bounds on the OBDD-size of integer multiplication via universal hashing ⋮ The nonapproximability of OBDD minimization ⋮ On the hardness of approximating the minimum consistent acyclic DFA and decision diagram. ⋮ Optimizing Probabilities in Probabilistic Logic Programs ⋮ Fault tree analysis: a survey of the state-of-the-art in modeling, analysis and tools
This page was built for publication: Improving the variable ordering of OBDDs is NP-complete
