THE HAMILTONIAN COMPLETION PROBLEM AND ITS SOLUTION
Victor J. Rayward-Smith · Engineering Optimization · 1987
The Hamiltonian completion problem for an arbitrary graph. G. is the determination of the smallest number of new edges which must be added to G to make the resulting graph Hamilltonian. For general graphs, the associated decision problem is NP-complete although polynomial time algorithms do exist for special cases. In this paper, we review the known results concerning Hamiltonion completion and develop a suite of exact and approximate solution algorithms. Guidelines are given as to which of the various algorithms should be used in given circumstances