An efficient approach to decomposition of multi-output Boolean functions with large sets of bound variables

Finding appropriate bound sets of variables is the most important task of functional decomposition. When solving some problems, the bound sets need to be larger, for instance in decomposition to symmetric subfunctions realized in MOPS arrays for submicron technologies, or when no good small bound sets exist. In such cases, the creation of the incompatibility graph, which is necessary to evaluate good variable partitionings, becomes very inefficient. Therefore, an algorithm is proposed that can speed up this process by orders of magnitude without sacrificing the quality of the decomposition, because the same graph coloring algorithms (exact or approximate) are still applied to the created graph