Improving the variable ordering of OBDDs is NP-complete
From MaRDI portal
Publication:4420841
DOI10.1109/12.537122zbMath1048.68571WikidataQ56340203 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
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
On the Influence of the State Encoding on OBDD-Representations of Finite State Machines, Unnamed Item, The Decomposition Tree for analyses of Boolean functions, Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems, String-matching with OBDDs, On the effect of local changes in the variable ordering of ordered decision diagrams, On reachability and controllability of switched Boolean control networks, Weighted \(A^*\) search - unifying view and application, An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints, 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, 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, Minimization problems for parity OBDDs, 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., On Application of Multi-Rooted Binary Decision Diagrams to Probabilistic Model Checking, Hierarchical Set Decision Diagrams and Automatic Saturation, On the OBDD Complexity of Threshold Functions and the 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
