# A hybrid minimum spanning tree method for traveling salesman problem

**Hehua Li ^{1}, Wei Xiong^{1}, Yong Wang^{2}**

COMPUTER MODELLING & NEW TECHNOLOGIES 2014 **18**(12C) 40-45

^{1}Institute of Information Security Technology, Chongqing College of Electronic Engineering, Chongqing 401331, China

^{2}North China Electric Power University, Beijing 102206, China

Traveling salesman problem (TSP) has a wide range of applications in communication, transportation, manufacturing etc. However, it is proven to be NP-complete in mathematics. An approximate method based on the Minimum Spanning Tree (MST) with an optimal four-vertex path is presented for the triangle TSP. We first compute the MST with a complete weighted graph. Then an Eulerian graph is generated by doubling the edges of the MST from an initial vertex. The optimal four-vertex path is used to simplify the Eulerian graph into a Hamiltonian cycle. Different from the common MST heuristics for TSP, all the generated four-vertex paths in the Hamiltonian cycle are the optimal four-vertex paths. Therefore, the approximation computed with the hybrid MST method is generally shorter than that produced with the common MST heuristics. The experiments for the Euclidean TSP examples also give the same conclusion.