• Mohan.S
• Anitha .B
• Divya. s

This paper propose a comparison study on a heuristic to find Travelling Salesman Tour(TST) in a connected network. The approach first identifies a vertex and two associated edges that are desirable for inclusion in the required TST. If we let this vertex be denoted by p and two selected edges emanating from this vertex be denote (p,q) and (p,k) then we find a path joining the two vertex q and k passing through all the remaining vertex of the given network . A sum of these lengths, That is length of the links (p,q) an (p,k) along with the length of the path that joins the vertex p an q passing through all remaining vertices will results feasible TST, hence gives an upper bound on the TST. A simple procedure is outlined to identify: (1) the vertex p, (2) the two corresponding links (p,q) and (p,k) and (3) the path joining the vertex q and k passing through all the remaining vertex. The approach is based on the minimum spanning tree; hence the complexity of the TST is reduced. Thes network in the present context has been assume to be connected network with at least two edges emanating from each vertex.

Connected network, Minimum Spanning Tree, Travelling Salesman Tour

"A COMPARATIVE STUDY ON A MINIMUM SPANNING TREE BASED HEURISTIC FOR THE TRAVELLING SALESMAN TOUR ", International Journal of Emerging Technologies and Innovative Research (www.jetir.org), ISSN:2349-5162, Vol.6, Issue 4, page no.379-388, April-2019, Available :http://www.jetir.org/papers/JETIR1904670.pdf

"A COMPARATIVE STUDY ON A MINIMUM SPANNING TREE BASED HEURISTIC FOR THE TRAVELLING SALESMAN TOUR ", International Journal of Emerging Technologies and Innovative Research (www.jetir.org | UGC and issn Approved), ISSN:2349-5162, Vol.6, Issue 4, page no. pp379-388, April-2019, Available at : http://www.jetir.org/papers/JETIR1904670.pdf