Size of ordered binary decision diagrams representing threshold functions

DOI10.1016/S0304-3975(97)83807-8MaRDI QIDQ1390857zbMATH OpenOpenAlexFDO

Authors K. Hosaka, T. Kaneda, Y. Takenaga, S. Yajima

Publication date 22 July 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(97)83807-8

zbMATH Keywords

Boolean functionthreshold functionsordered binary decision diagram

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 1555979
• scientific article; zbMATH DE number 1088264
• On the size of (generalized) OBDDs for threshold functions
• On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
• Exact OBDD Bounds for Some Fundamental Functions

Cites work

• scientific article; zbMATH DE number 1354131 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• A Lower Bound of the Number of Threshold Functions
• Binary Decision Diagrams
• Finding the optimal variable ordering for binary decision diagrams
• Graph-Based Algorithms for Boolean Function Manipulation
• On Complete Sets of Logic Primitives
• On the OBDD-representation of general Boolean functions
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication

Cited in

(17)

• On the size of (generalized) OBDDs for threshold functions
• scientific article; zbMATH DE number 1555979 (Why is no real title available?)
• Non-clausal redundancy properties
• On the size of binary decision diagrams representing Boolean functions
• Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
• Size of OBDD representation of 2-level redundancies functions
• SIZES OF ORDERED DECISION TREES
• On threshold BDDs and the optimal variable ordering problem
• Forms of representation for simple games: sizes, conversions and equivalences
• Clausal proofs for pseudo-Boolean reasoning
• Theoretical insights and algorithmic tools for decision diagram-based optimization
• On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
• On the Width of Ordered Binary Decision Diagrams
• Yet harder knapsack problems
• Binary decision diagrams for generating and storing non-dominated project portfolios with interval-valued project scores
• Compact representation of near-optimal integer programming solutions
• Ordered binary decision diagrams and the Shannon effect

This page was built for publication: Size of ordered binary decision diagrams representing threshold functions

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