Yu-Chen/Kaufmann algorithm - Travelling salesman problem

This is an combined algorithm that produces all the roads on a graph and that can be used also for cost problems, not only for minimal cost, also for maximum cost road/cycle problems.
It is known that the Dijkstra algorithm can be applied only for the minimal road/cycle.

Let’s consider the graph with 4 nodes given by the following matrix:
A = 0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
If we want to determine the Hamiltonian circuits we can use a combination of two algorithms: Kaufmann and Strassen.

Using the Kaufmann algorithm we obtain by calculus:

L = 0 12 13 0
21 0 0 24
31 0 0 34
0 42 43 0

L~ = 0 2 3 0
1 0 0 4
1 0 0 4
0 2 3 0

L2 = L * L~

From the Stassen algorithm we obtain:

M1 = 123,341 0
0 214,432

M2 = 341 312
421 432

M3 = -123 124
213 214

M4 = -341 342
431 -432

M5 = 123 134
243 214

M6 = 0 312,-124
-213,421 0

M7 = 0 134,-342
-431,243 0

C11 = 0 0
0 0
C12 = 0 124,134
213,243 0

C21 = 0 312,342
421,431 0

C22 = 0 0
0 0

If we want to determine all the circuits with length 1->n, this algorithm is polinomial.
For each step – each Lk (the k-th power of L), using the Stassen algorithm we use k^(log2 (7)) steps; if we want to determine all the circuits we have to done S operation, where S = sum(x^i) with x from 1-n and i = log2 (7).
We can see an explanation of how to compute all these sums on:
http://mathforum.org/library/drmath/view/56018.html

So, the algorithm Kaufmann-Stassen for determine the Hamiltonian circuits is of order O(n^x) where x = log2 (7) + 1.

Bibliography:

1.http://en.wikipedia.org/wiki/Strassen_algorithm">http://en.wikipedia.org/wiki/Strassen_algorithm

2. www.asecib.ase.ro/Mitrut%20Dorin/Curs/bazeCO/doc/33Grafuri.doc

3.http://mathforum.org/library/drmath/view/56018.html

The hamiltonian cycles on a graph can be determined by combining the two algorithms:
Yu-Chen - Latin matrix and the Strassen product of matrices. In this case the algorithm will be faster than the classic method using the DF visiting method.

This algorithm can be used for the robots that produce PCBs; instead of using only one "hand" the robot can use more "hands" and can begin for multiple corners.