On the effect of local changes in the variable ordering of ordered decision diagrams

DOI10.1016/0020-0190(96)00119-6zbMath0875.68432WikidataQ127293120 ScholiaQ127293120MaRDI QIDQ671612

Beate Bollig, Ingo Wegener, Martin Loebbing

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00119-6

zbMATH Keywords

Algorithms; Computational complexity; Variable ordering

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems, Worst case examples for operations on OBDDs, On symbolic OBDD-based algorithms for the minimum spanning tree problem, On efficient implicit OBDD-based algorithms for maximal matchings, Implicit computation of maximum bipartite matchings by sublinear functional operations, BDDs -- design, analysis, complexity, and applications., Randomized OBDD-based graph algorithms, The nonapproximability of OBDD minimization, Priority functions for the approximation of the metric TSP, Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations, Randomized OBDD-Based Graph Algorithms

Cites Work

• On the relation between BDDs and FDDs
• Graph-Based Algorithms for Boolean Function Manipulation
• Improving the variable ordering of OBDDs is NP-complete
• Unnamed Item
• Unnamed Item