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

(19)

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

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)