Bounds of Travelling Salesman Problem: A Technical Note

By Fozia Hanif Khan, Nasiruddin Khan, Syed Inayatullah, Shaikh Tajuddin Nizami

Abstract

Purpose of this paper is to highlight, an algorithm which is provided by the Cristo Nicos in (1972) is an incorrect algorithm for finding the lower bound for TSP, here we are discussing the mistake of the algorithm and also calculating the best possible value of lower bound of the problem mentioned in (Ctisto 1972), by using the same algorithm but this value could not be calculated by the author.

 

Key Words : Lower bound, travelling salesman problem, symmetric TSP

 

Click here to download the complete article in PDF Format