binary decision diagram

A binary decision diagram (or BDD) is a decision diagram representing a boolean function : Bⁿ -> B.
The values of the sinks are {0,1}, the are exactly two outgoing edges at every non-sink node, marked with 0 or 1.
A BDD is called ordered if one every path from the source to the sink the variables turn up in the same fixed order and every variable turns up at most once.
A BDD is called reduced if it is ordered and there are no isomorphic subgraphs in the BDD. They are often called ROBDDs or OBDDs (the second is a little bit confusing, but standard nowadays).

Why are they important ?

In automatic digital circuit designs you have to deal with extremely large boolean functions. Think of a 32 bit multiplier. So you need a handy representation for them. Boolean formulas are often large and most important not canonical. If they are restricted to SOPs or the like, they usually get much too large to handle. Function tables are too large anyway. So you have of problem. OBDD are really small representations for some functions (often used functions !), canonical (for a fixed order of variables) and there are fast algorithms for them. So they play an important role in automatic digital circuit design, in fact they are very often used. Howevery, some problems remain: there are functions for which you can prove that all representing OBDDs have at least expotential size (in respect to the number of variables). A multiplier contains such functions. Note that there must be such functions, unless P=NP. (A OBDD is a satisfiability test !)