A neural algorithm to solve the Hamiltonian cycle problem

A network of analog neurons to solve the Hamiltonian cycle problem (HCP) is described. This neural net is a modification of the network proposed by Hopfield to solve the traveling salesman problem (TSP). A result on the convergence of quasi-stationary flow and a bound for the strength of an inhibitory self-connection are presented. Results of successful experiments with graphs of up to 500 nodes are reported. The result of an experiment with the 318-city TSP is also reported. Contrary to intuition, the performance improves with the size of the graphs. The 20-node graphs fail to give consistent results for 10% connectivity, while 400- and 500-node graphs were solved successfully