On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem

DOI10.1007/978-3-540-95891-8_15MaRDI QIDQ3599068zbMATH OpenOpenAlexFDO

Authors Beate Bollig

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-95891-8_15

zbMATH Keywords

computational complexityordered binary decision diagramsthreshold functionsvariable ordering problem

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the size of (generalized) OBDDs for threshold functions
• scientific article; zbMATH DE number 1088264
• Size of ordered binary decision diagrams representing threshold functions
• scientific article; zbMATH DE number 1555979
• On the Width of Ordered Binary Decision Diagrams

Cites work

• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Branching Programs and Binary Decision Diagrams
• Exact OBDD Bounds for Some Fundamental Functions
• Experimental and Efficient Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 3594626 (Why is no real title available?)
• scientific article; zbMATH DE number 1222598 (Why is no real title available?)
• scientific article; zbMATH DE number 1088264 (Why is no real title available?)
• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Improving the variable ordering of OBDDs is NP-complete
• Mathematical Foundations of Computer Science 2003
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• On Threshold BDDs and the Optimal Variable Ordering Problem
• Reduction of OBDDs in linear time
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Size of ordered binary decision diagrams representing threshold functions
• Symbolic graphs: Linear solutions to connectivity related problems
• Symbolic topological sorting with OBDDs

Cited in

(10)

• On threshold BDDs and the optimal variable ordering problem
• Size of ordered binary decision diagrams representing threshold functions
• On Threshold BDDs and the Optimal Variable Ordering Problem
• scientific article; zbMATH DE number 1222599 (Why is no real title available?)
• scientific article; zbMATH DE number 1222600 (Why is no real title available?)
• scientific article; zbMATH DE number 1088264 (Why is no real title available?)
• scientific article; zbMATH DE number 1555979 (Why is no real title available?)
• On the complexity of constructing optimal ordered binary decision diagrams
• ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
• On the size of (generalized) OBDDs for threshold functions

Describes a project that uses

Uses Software

• azove

This page was built for publication: On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem

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