I am giving a very simple explanation of the algorithm so that it becomes easier to understand.

The main advantage of this approach is that the exact solution can be obtained for "complete" graphs in polynomial time. ( Please note that the word "complete" which is mentioned here is the same mathematical term used in graph theory ). I tried out the "complete" graph examples in the textbook using pen and paper and they are giving the exact solutions. Now the only thing is that solution needs to be tested on further complete graph examples using computers and software by scientists. Also the solution is polynomial time, because the solution is a new type of modified and improved version of the nearest neighbour method. And everyone knows that the nearest neighbour method is an approximate method which is polynomial time method. But this new modified method, gives exact solution to "complete" graphs and it is polynomial time also.

In graph theory, a complete graph of n vertices has [ n(n-1)/2 ] edges. So when implementing the algorithm, in the worst case, all the edges may have to be taken for processing. Also for each edge, the left vertex and the right vertex has to be taken for processing. So the number of times the edges have to be taken for processing = number of edges * 2 = [ n(n-1)/2] * 2 = n(n-1) = n^2 - n . So the processing time for the algorithm in the worst case = O(n^2) ie:- it takes polynomial time. ( Here "^" means raised to ). In the example that I have given for describing how the algorithm works, I have taken a random edge in order to show how the algorithm works. Where the algorithm is taken with the minimum weight edge , the process is shown between the headings "Beginning of second example" and"End of second example" and this description is short and easy for viewing.

I am claiming that I have tried the algorithm on all the examples given in the theory sections of the 2 textbooks and they give exact solutions. But I dont have mathematical proof. For graphs that are not complete, I cannot claim that it will give the exact solution, but I can only say that they might give the best solution. That is how far have I have tested. For other scientists, to get further convinced, it is better, if they try out this algorithm on more complete graphs at least using pen and paper for the time being instead of using computers. I am not forcing anyone to try it out. A lot of Mathematicians are saying that there might never be a solution to this problem, so I thought it was a little exciting if this algorithm would provide any clue which could further advance the research of the scientists. For proof of such problems, advanced degrees in maths is required like B.Sc, M.Sc, PhD etc. I don't even have a B.Sc degree, but only a B.Tech Degree. But the mathematics that I have learnt in B.Tech is not formal enough for finding a proof of such theorems. I can say that what I have given in the post is a " conjecture ". This word is more suitable.

I will try to put the explanation of the algorithm in very simple terms as far as possible. All Discrete Mathematicians know about the nearest neighbour method. In the nearest neighbour method, a random edge is taken and the nearest neighbour method is applied starting from that edge. This is the method that is known that is known to everyone. So when the nearest neighbour method is done, the process is O(1). Now in my method ( if for example the worst case is taken ie:- every edge of the complete graph is taken ( Also suppose the complete graph consists of "n" edges. ) ) , then the nearest neighbour method is applied to each edge ( taking the most minimum weight edge first and proceeding in ascending order of the weights of the edges ) , then the number of hamilton circuits obtained will be "n" hamilton circuits. So now the order will be O(n) because of "n" edges. Now the most important part of the algorithm is that for each edge, the nearest neighbour method should be applied by starting from the left vertex of the edge and then the next hamilton circuit should be obtained by starting from the right vertex of the edge by using the nearest neighbour method. So each edge should contain two hamilton circuits (which is obtained by using the nearest neighbour method ). So now the total number of hamilton circuits obtained for "n" edges will be " 2*n " hamilton circuits. So now the the order is O(2n) ie:- O(n). ( Please note that here the number of edges is taken as "n" and not the number of vertices , for easy understanding.) The most important point is that for each edge, 2 hamilton circuits are required which are produced by starting from the left vertex and the other by starting from the right vertex of the edge.

So the software for this algorithm is already there ie:- nearest neighbour method programs. The only modification that is needed for the software is that the nearest neighbour method should be applied to each edge, and for each edge, the nearest neighbour method should be applied to the left vertex and the right vertex of each edge. So for a complete graph of "n" vertices, in the worst case, there are "2n" hamilton circuits. Then the minimum weight hamilton circuit among all these hamilton circuits is taken as the shortest weight hamilton circuit.

End of posting