On threshold BDDs and the optimal variable ordering problem

DOI10.1007/S10878-007-9123-ZzbMATH Open1183.68411OpenAlexW2797533443MaRDI QIDQ1016038FDOQ1016038

Authors 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

binary decision diagramknapsack\(0/1\) integer programmingoptimal variable orderingthreshold BDDvariable ordering spectrum

Mathematics Subject Classification ID

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

Recommendations

• On Threshold BDDs and the Optimal Variable Ordering Problem
• On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
• scientific article; zbMATH DE number 1088264
• scientific article; zbMATH DE number 1222600
• Improving the variable ordering of OBDDs is NP-complete
• scientific article; zbMATH DE number 1222599
• On the size of (generalized) OBDDs for threshold functions
• ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1220670 (Why is no real title available?)
• scientific article; zbMATH DE number 1995157 (Why is no real title available?)
• Branching Programs and Binary Decision Diagrams
• Experimental and Efficient Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• Hard examples for resolution
• Improving the variable ordering of OBDDs is NP-complete
• Lectures on Polytopes
• SATLIB: An online resource for research on SAT
• Size of ordered binary decision diagrams representing threshold functions

Cited in

(11)

• Variable ordering for decision diagrams: a portfolio approach
• Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
• On the use of binary decision diagrams for solving problems on simple games
• Forms of representation for simple games: sizes, conversions and equivalences
• azove
• On Threshold BDDs and the Optimal Variable Ordering Problem
• Quantum Differential Evolution Algorithm for Variable Ordering Problem of Binary Decision Diagram
• Power indices of simple games and vector-weighted majority games by means of binary decision diagrams
• Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
• Compact representations of all members of an independence system
• On finding the optimal BDD relaxation

Describes a project that uses

Uses Software

• SATLIB
• CUDD

This page was built for publication: On threshold BDDs and the optimal variable ordering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016038)