On the size of (generalized) OBDDs for threshold functions

DOI10.1016/j.ipl.2009.01.005zbMath1209.68151OpenAlexW2161264634MaRDI QIDQ987805

Beate Bollig

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.01.005

zbMATH Keywords

computational complexityordered binary decision diagramsthreshold functionsbranching programs

Mathematics Subject Classification ID

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

Related Items (2)

Yet harder knapsack problems ⋮ On the minimization of (complete) ordered binary decision diagrams

Uses Software

• azove

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 Threshold BDDs and the Optimal Variable Ordering Problem
• Graph-Based Algorithms for Boolean Function Manipulation
• 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

This page was built for publication: On the size of (generalized) OBDDs for threshold functions