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

DOI10.1016/0020-0190(96)00119-6zbMath0875.68432OpenAlexW1977533508WikidataQ127293120 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

AlgorithmsComputational complexityVariable ordering

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

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

Cites Work

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

This page was built for publication: On the effect of local changes in the variable ordering of ordered decision diagrams