ZDDs

Let U (the universe) be the set of all countries on a map. Any selection of non-adjacent countries can be viewed as a subset of U.
Consider F, the set of all such subsets. For clarity, we call a set of subsets of U such as F (equivalently, a subset of the power set of U) a family of sets over U. Thus "set" usually means a subset of U, and "family" means a collection of these subsets. Hypergraphs are equivalent to families of sets, but we follow Knuth’s lead and prefer "families" over "hypergraphs", due to greater familiarity.
It turns out we can describe F in terms of basic families that by themselves are easy to describe. If we had a clever method to represent families on a computer, we might be able to quickly construct a representation for F from the basic families. If the method were really clever, we could subsequently determine the set in F of maximum weight, and solve the problem.
A ZDD is a really clever data structure that represents a family of sets. ZDD stands for zero-suppressed binary decision diagram but this is unimportant.
Combinatorial problems such as the above can be viewed as asking questions about a particular family of sets. With ZDDs, we can answer them efficiently.

Add comment

Security code
Refresh