Abstract
Binary Decision Diagram (BDD), proposed by Akers, is a directed acyclic graph, which represents
many boolean functions efficiently. After Bryant proposed an efficient algorithm to manipulate them,
BDD is used not only in logic design area, but also in combinatorial problems. The size of a BDD
sometimes highly depends on its variable ordering and the size of an intermediate BDD also depends
on the operation ordering. It is, therefore, important to find a good variable ordering and an operation
ordering.
In this paper, we take an independent set problem. It is easy to construct a BDD of independent sets,
but it is difficult to construct a BDD of maximal independent sets. We present an algorithm to construct
a BDD of maximal independent sets of a graph from a BDD of independent sets of it and consider the
size of the BDD and operation ordering. As a result, we found that our algorithm reduced the size of the
intermediate BDD. The resulting BDD represents prime implicants of a boolean function, therefore this
problem is regarded as a problem of generating prime implicants of a negative 2-CNF function. Besides,
this approach can be used for counting the number of triangulations and we found BDD represents the
solutions compactly.