Beyond combinatorial explosion

Suppose that we want to divide the employees of a company into two equal groups. How many different groupings exist? The number of different groupings increases exponentially with the number of employees. This phenomenon is called combinatorial explosion. Trying to solve problems that involve combinatorial explosion by using naive algorithms becomes impractical even if we use very fast modern computers. In this talk, we describe how the number of combinations created by combinatorial explosion can be counted by algorithms based on the data structure called Binary Decision Diagrams (BDD). The utility of this counting operation is confirmed by some concrete examples.