On threshold BDDs and the optimal variable ordering problem

DOI10.1007/s10878-007-9123-zzbMath1183.68411OpenAlexW2797533443MaRDI QIDQ1016038

Markus Behle

Publication date: 4 May 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9123-z

zbMATH Keywords

knapsackbinary decision diagram\(0/1\) integer programmingoptimal variable orderingthreshold BDDvariable ordering spectrum

Mathematics Subject Classification ID

Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items

On the use of binary decision diagrams for solving problems on simple games, Decision Diagrams for Discrete Optimization: A Survey of Recent Advances, Forms of representation for simple games: sizes, conversions and equivalences, Power indices of simple games and vector-weighted majority games by means of binary decision diagrams, On finding the optimal BDD relaxation, azove

Uses Software

• SATLIB
• CUDD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Size of ordered binary decision diagrams representing threshold functions
• Graph-Based Algorithms for Boolean Function Manipulation
• Hard examples for resolution
• Lectures on Polytopes
• Improving the variable ordering of OBDDs is NP-complete
• Branching Programs and Binary Decision Diagrams
• Experimental and Efficient Algorithms