  A new characterisation of Hamiltonian graphs using f-cutset matrix is
proposed. A new exact polynomial time algorithm for the travelling salesman
problem (TSP) based on this new characterisation is developed. We then define
so called ordered weighted adjacency list for given weighted complete graph and
proceed to the main result of the paper, namely, the exact algorithm based on
utilisation of ordered weighted adjacency list and the simple properties that
any path or circuit must satisfy. This algorithm performs checking of
sub-lists, containing (p-1) entries (edge pairs) for paths and p entries (edge
pairs) for circuits, chosen from ordered adjacency list in a well defined
sequence to determine exactly the shortest Hamiltonian path and shortest
Hamiltonian circuit in a weighted complete graph of p vertices. The procedure
has intrinsic advantage of landing on the desired solution in quickest possible
time and even in worst case in polynomial time. A new characterisation of
shortest Hamiltonian tour for a weighted complete graph satisfying triangle
inequality (i.e. for tours passing through every city on a realistic map of
cities where cities can be taken as points on a Euclidean plane) is also
proposed. Finally, we propose a classical algorithm for unstructured search and
also three new quantum algorithms for unstructured search which exponentially
speed up the searching ability in the unstructured database and discuss its
effect on the NP-Complete problems.
