BDDs—design, analysis, complexity, and applications

✍ Scribed by Ingo Wegener

• Book ID: 104294227
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 776 KB
• Volume: 138
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00297-x

✦ Synopsis

BDDs (binary decision diagrams) and their variants are the most frequently used representation types or data structures for boolean functions. Research on BDD variants has turned out to be one of the areas where the symbiosis between theoretical investigations in algorithm design and analysis, complexity theory, and applications has led to progress in theory and in applications. Here the di erent roots of the interest in BDDs are described, the main BDD variants and their algorithmic properties are presented, the representation size of selected functions is investigated, lower bound techniques are discussed and applications to algorithmic graph problems and hardware veriÿcation problems are presented.