Improving the variable ordering of OBDDs is NP-complete

DOI10.1109/12.537122zbMath1048.68571WikidataQ56340203 ScholiaQ56340203MaRDI QIDQ4420841

Beate Bollig, Ingo Wegener

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

zbMATH Keywords

NP-completeness; graph algorithms; Ordered binary decision diagrams

Mathematics Subject Classification ID

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, FINDING SMALL EQUIVALENT DECISION TREES IS HARD, The Decomposition Tree for analyses of Boolean functions, Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems, Augmenting measure sensitivity to detect essential, dispensable and highly incompatible features in mass customization, Characteristics of the maximal independent set ZDD, On the minimization of (complete) ordered binary decision diagrams, 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, 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, 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, Minimization problems for parity OBDDs, Fault tree analysis: a survey of the state-of-the-art in modeling, analysis and tools, 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., 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, 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