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

DOI10.1007/978-3-540-95891-8_15zbMath1206.68100OpenAlexW1515120539MaRDI QIDQ3599068

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

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

Uses Software

• azove

Cites Work

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