Patent Document ID: 20090319465
Application ID: 12213303
Patent Flag: 0

Claim One:
1. A method of solving the problem of decision (testing if, given a finite number of transformations (the generators) which can be applied to a finite number of elements, the corresponding n-generated discrete object (the input) has a hamiltonian cycle and/or path), of searching (obtaining the explicit construction of one several or all the hamiltonian cycles and or paths of the given input), counting (obtaining an upper bound of the number of Hamiltonian cycles and/or paths of the given input) and optimizing (selecting one of several hamiltonian cycles and/or paths solutions according to an specified criterion) the said method comprising the following steps: a pre-processing step which decomposes the input in sub inputs of pairs of generators; a first step (step 1) consisting of the classification of a given sub input in one of several classes by testing if one to one of three possible relations holds; a second (step 2) consisting in the determination of the number of possible ending vertices in the hamiltonian cycle or paths of the sub input and in the determination of which are the possible ending vertices in a hamiltonian cycle or path of the sub input; a third step (step 3) which based on the value of two parameters discards in which of the possible ending vertices of the sub input can not the hamiltonian cycle or path end; a fourth step (step 4) which consist in a test of a structural property (smoothness) on a sub digraph of the sub input and classifies it according to its expected hardness; a fifth step (step 5) which consist in a test another structural property (entanglement) on a sub digraph the sub input based on the intersection of the sets generated by sequences of generators; a sixth step (step 6) which consist in a test of another structural property (cycle-entanglement) on a sub digraph of the sub input; a seventh step (step 7) which is first a reduction transformation to the sub input into an object of the same kind but of a reduced size, and second a decision about the hamiltonian property based on a two parameters of the reduced object; an eighth step (step 8) which by the activation of several non-contradictory one-generator cycle detects 1-compact or n-compact sub inputs; a ninth step (step 9) which consists in the selection of a given vertex in the sub input as ending vertex and then applies 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 a list of specified sub digraphs until no more changes happens, a tenth step (step 10) which consists in the iteration of: the selection of 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 the number of hamiltonian cycles and paths, and 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 a list of specified sub digraphs until no more changes happens, until a hamiltonian cycle or path is found or a conclusion that the sub digraph has no hamiltonian cycle or path is reached.