The Shortest Hamiltonian Chain of a Graph

Given a graph G with weighted links, the problems considered in this paper are the following: (i) Find the shortest possible Hamiltonian chain (HC) of the graph G when the end vertices are not specified. (ii) Find the shortest possible HC of G when the end vertices are specified.Two basic algorithms are given each of which can solve both of the above problems with only slight modification. The first algorithm, A, is based on a decision-tree search with lower bounds used to limit the search. The second algorithm, B, is a fast iterative procedure which is based on simple transformations of the cost matrix of the graph G, ensuring at each step that the relative cost of all Hamiltonian chains stay unchanged.Both algorithms ensure the optimality of the final answer, but whereas the convergence of Algorithm A is self-evident, no proof of convergence has been obtained for Algorithm B. However, tests of Algorithm B (which is both simpler and computationally superior to Algorithm A) on a number of sample problems ...