Algebraic decision diagram
An algebraic decision diagram (ADD) or a multi-terminal binary decision diagram (MTBDD), is a data structure that is used to symbolically represent a Boolean function whose codomain is an arbitrary finite set S. An ADD is an extension of a reduced ordered binary decision diagram, or commonly named binary decision diagram (BDD) in the literature, which terminal nodes are not restricted to the Boolean values 0 (FALSE) and 1 (TRUE). The terminal nodes may take any value from a set of constants S.

Definition 

An ADD represents a Boolean function from   to a finite set of constants S, or carrier of the algebraic structure. An ADD is a rooted, directed, acyclic graph, which has several nodes, like a BDD. However, an ADD can have more than two terminal nodes which are elements of the set S, unlike a BDD. An ADD can also be seen as a Boolean function, or a vectorial Boolean function, by extending the codomain of the function, such that  with  and  for some integer n. Therefore, the theorems of the Boolean algebra applies to ADD, notably the Boole's expansion theorem. Each node of is labeled by a Boolean variable and has two outgoing edges: a 1-edge which represents the evaluation of the variable to the value TRUE, and a 0-edge for its evaluation to FALSE. An ADD employs the same reduction rules as a BDD (or Reduced Ordered BDD):

 merge any isomorphic subgraphs, and
 eliminate any node whose two children are isomorphic. ADDs are canonical according to a particular variable ordering. Matrix partitionning 
An ADD can be represented by a matrix according to its cofactors. Applications 

ADDs were first implemented for sparse matrix multiplication and shortest path algorithms (Bellman-Ford, Repeated Squaring, and Floyd-Warshall procedures). See also 

 Binary decision diagram
 Zero-suppressed decision diagram

References

Diagrams
Graph data structures