A zero-suppressed decision diagram (ZSDD or ZDD) is a version of binary decision diagram

Binary decision diagram

In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...

 (BDD) where instead of nodes being introduced when the positive and the negative part are different, they are introduced when negative part is different from constant 0. A Zero-suppressed

Zero suppression

Zero suppression is the removal of redundant zeroes from a number. This can be done for storage, page or display space constraints or formatting reasons, such as making a letter more legible.Examples:*00049823 → 49823*7.678600000 → 7.6786...

 decision diagram is also commonly referred to as a zero-suppressed binary decision diagram (ZBDD).

They are useful when dealing with functions that are almost everywhere 0.

Available packages

• CUDD: A BDD package written in C that implements BDDs and ZBDDs, University of Colorado, Boulder
• JDD, A java library that implements common BDD and ZBDD operations

External links

• Alan Mishchenko, An Introduction to Zero-Suppressed Binary Decision Diagrams
• Donald Knuth
  Donald Knuth
  Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
  
  , Fun With Zero-Suppressed Binary Decision Diagrams (ZDDs) (video lecture, 2008)