Patent ID: 8583591

Claim:
A method comprising: by one or more computing devices, accessing a binary decision diagram (BDD) representing a function having n variables, where n≧2, wherein: the BDD comprises n layers corresponding to the n variables, respectively, each of the n layers comprising one or more decision nodes; a size of each of the n layers is based on the number of decision nodes at the each layer; and a size of the BDD is based on the sum of respective sizes of the n layers of the BDD; and reordering the n variables of the BDD by iteratively moving k variables of the n variables to their locally optimum layers, where k≧2, until a size of the BDD has reached a desired threshold, wherein each iteration comprises: selecting from the n layers k layers that currently have the k largest sizes among the n layers, wherein the k variables are currently positioned at the k layers; concurrently moving the k variables to different layers of the BDD until each of the k variables has been at all the n layers to determine a locally optimum layer for each of the k variables, wherein the locally optimum layer of a variable during each iteration is one of the n layers that currently yields a smallest size among the n layers with the variable at each of the n layers; and concurrently moving the k variables to their respective locally optimum layers.