BDDs -- design, analysis, complexity, and applications.
type: Item
instance of: scholarly article
title: BDDs -- design, analysis, complexity, and applications.
zbMATH Open document ID: 1045.94023
DOI: 10.1016/S0166-218X(03)00297-X
author: Ingo Wegener
published in: Discrete Applied Mathematics
publication date: 2004-03-29T00:00:00Z
review text: A binary decision diagram (BDD) is a labelled acyclic graph that represents some Boolean functions. They, and similar devices, are used in many different fields such as hardware design and verification, the design and analysis of algorithms, computational complexity theory, and model checking. This paper is a highly readable survey of BDDs, their variants and various uses. Real world applications are emphasized and illustrated by examples.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 2062826
zbMATH Keywords: binary decision diagrams
zbMATH Keywords: complexity classes
zbMATH Keywords: truth functions
zbMATH Keywords: switching circuits
zbMATH Keywords: design of algorithms
zbMATH Keywords: model checking
describes a project that uses: CUDD
MaRDI profile type: Publication
cites work: Higher-Radix Division Using Estimates of the Divisor and Partial Remainders
cites work: Time-space tradeoffs for branching programs
cites work: On the effect of local changes in the variable ordering of ordered decision diagrams
cites work: Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
cites work: Improving the variable ordering of OBDDs is NP-complete
cites work: Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
cites work: Q2754143
cites work: A read-once branching program lower bound of Ω(2 n/4 ) for integer multiplication using universal hashing
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
cites work: Q4267798
cites work: Efficient Boolean manipulation with OBDD's can be extended to FBDD's
cites work: Q4337605
cites work: Communication Complexity
cites work: Q5628016
cites work: An \(O(IVI^3)\) algorithm for finding maximum flows in networks
cites work: Q5545524
cites work: A Lower Bound for Integer Multiplication with Read-Once Branching Programs
cites work: Optimal ordered binary decision diagrams for read-once formulas
cites work: Reduction of OBDDs in linear time
cites work: Graph driven BDDs -- a new data structure for Boolean functions
cites work: Q4287364
cites work: On the complexity of branching programs and decision trees for clique functions
cites work: Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
cites work: Branching Programs and Binary Decision Diagrams
cites work: Q2762533
cites work: Q3347300
description: scientific article; zbMATH DE number 2062826