Patent Document ID: 8266089
Application ID: 12213303
Patent Flag: 1

Claim One:
1. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising the following steps: a pre-processing step including decomposing an input in sub inputs of pairs of generators; a first step (step 1) including classifying a given sub input in one of several classes by testing if one to one of three possible relations holds; a second step (step 2) including determining a number of possible ending vertices in a hamiltonian cycle or path of the sub input and determining which are the possible ending vertices in the hamiltonian cycle or path of the sub input; a third step (step 3) including discarding the possible ending vertices of the sub input that cannot be the hamiltonian cycle or path end based on a value of two parameters; a fourth step (step 4) including testing a structural property on a sub digraph of the sub input and classifying it according to its expected hardness; a fifth step (step 5) including testing another structural property on a sub digraph of the sub input based on an intersection of sets generated by sequences of generators; a sixth step (step 6) including testing another structural property on a sub digraph of the sub input; a seventh step (step 7) including first reducing, by a reduction transformation, the sub input into an object of a same kind but of a reduced size, and second deciding about a hamiltonian property based on two parameters of the reduced object; an eighth step (step 8) including detecting 1-compact or n-compact sub inputs by activation of several non-contradictory one-generator cycles; a ninth step (step 9) including selecting a given vertex in the sub input as an ending vertex and then applying a propagation including an arc-forcing subroutine and a starting- to ending-vertex-non-hamiltonian path checking plus a non hamiltonian-cycle checking by an iterative marking of a list of specified sub digraphs until no more changes happens; and a tenth step (step 10) including an iteration of: selecting a given arc of the sub input according to specified criteria, including the greedy criteria, the random criteria and the specific criteria for obtaining an upper bound on a number of hamiltonian cycles and paths, and applying a propagation consisting in an arc-forcing subroutine and a starting- to ending-vertex-non-hamiltonian path checking plus a non hamiltonian-cycle checking by the iterative marking of the list of specified sub digraphs until no more changes happens, until the hamiltonian cycle or path is found or a conclusion that the sub input and/or input has no hamiltonian cycle or path is reached.