Glossary

What is a ZDD?

A ZDD, or zero-suppressed decision diagram, is a BDD with a different reduction rule, designed for families of sets where each set contains few elements. Shin-ichi Minato introduced it in 1993; Knuth calls ZDDs one of the nicest ideas in the subject.

Taught in TAOCP 7.1.4 Binary Decision Diagrams (part 2)

The one rule that changes

A reduced BDD removes a node when both of its branches go to the same place. A ZDD instead removes a node when its HI branch goes to 0, meaning "this element is never in any set from here". For sparse families (most elements absent from most sets) that removes almost everything, so the ZDD is far smaller than the BDD of the same family.

What they are good for

Representing every solution of an exact cover problem at once, all simple paths in a graph, a dictionary of words, or prime implicants, and then counting, filtering and combining those families with a family algebra. Knuth covers them at the end of §7.1.4, in Volume 4A.

Questions

When should I use a ZDD instead of a BDD?

When the objects are sets with few members out of many possible elements. For general Boolean functions, a BDD is usually the better fit.