Optimal ordered binary decision diagrams for read-once formulas

DOI10.1016/S0166-218X(99)00210-3zbMath0983.94062OpenAlexW2071403142MaRDI QIDQ1570838

Martin Sauerhoff, Ralph Werchner, Ingo Wegener

Publication date: 21 April 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00210-3

zbMATH Keywords

Boolean functionsordered binary decision diagramsread-once formulasoptimal variable orderings

Mathematics Subject Classification ID

Related Items (1)

BDDs -- design, analysis, complexity, and applications.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On read-once threshold formulae and their randomized decision tree complexity
• The nonapproximability of OBDD minimization
• Learning Boolean read-once formulas over generalized bases
• The number of knight's tours equals 33, 439, 123, 484, 294---counting with binary decision diagrams
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• Learning read-once formulas with queries
• Improving the variable ordering of OBDDs is NP-complete
• Branching Programs and Binary Decision Diagrams
• Comments on "A characterization of binary decision diagrams"

This page was built for publication: Optimal ordered binary decision diagrams for read-once formulas