METHOD FOR SOLVING OPTIMIZATION PROBLEMS IN STRUCTURED COMBINATORIAL OBJECTS
First Claim
1. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising:
- decomposing an input into sub inputs as pairs of generators; and
classifying the sub inputs in one of several classes by testing if one to one of three possible relations holds.
0 Assignments
0 Petitions
Accused Products
Abstract
The present invention is a method of solving the decision, for example, testing if, given a finite number of transformations which can be applied to a finite number of elements, the corresponding n-generated discrete object has a hamiltonian cycle and/or path, searching, for example, obtaining the explicit construction of one several or all the hamiltonian cycles and or paths of the given input, counting, for example, obtaining an upper bound of the number of Hamiltonian cycles and/or paths of the given input and optimization, for example, selecting one of several hamiltonian cycles and/or paths solutions according to an specified criterion, versions of the hamiltonian traversal (cycle and/or path) problem in class of combinatorial discrete objects.
-
Citations
60 Claims
-
1. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising:
-
decomposing an input into sub inputs as pairs of generators; and classifying the sub inputs in one of several classes by testing if one to one of three possible relations holds. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14, 15, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60)
-
-
2. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising:
-
decomposing an input into sub inputs as pairs of generators; and determining a number of possible ending vertices in a hamiltonian cycle or path of the sub inputs and determining which are possible ending vertices in the hamiltonian cycle or path of the sub inputs. - View Dependent Claims (16, 17, 18, 19, 20)
-
-
3. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising:
-
decomposing an input into sub inputs as pairs of generators; and testing a structural property on a sub digraph of the sub inputs and classifying it according to its expected hardness. - View Dependent Claims (21, 22, 23, 24, 25)
-
-
4. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising:
-
decomposing an input into sub inputs as pairs of generators; and testing a structural property on a sub digraph of the sub inputs based on an intersection of sets generated by sequences of generators. - View Dependent Claims (26, 27, 28, 29, 30)
-
-
5. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising:
-
decomposing an input into sub inputs as pairs of generators; and testing a structural property on a sub digraph of the sub inputs, the structural property including cycle entanglement. - View Dependent Claims (31, 32, 33, 34, 35)
-
-
6. A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising:
-
decomposing an input into sub inputs as pairs of generators; and first reducing, by a reduction transformation, the sub inputs into an object of a same kind but of a reduced size, and second deciding a hamiltonian property based on two parameters of the reduced object. - View Dependent Claims (36, 37, 38, 39, 40)
-
Specification