Abstract: With the expansion of traveling salesman problem,the search space for optimal solution on the complete graph increases exponentially.The cutting edge algorithm is proposed to reduce the search space of the optimal solution for the traveling salesman problem.It proves that the probability that an optimal Hamiltonian cycle edge contained in the shortest paths in the optimal cycles of quadrilaterals is different from that for a common edge.A number of shortest paths in the optimal cycles of quadrilaterals are selected to compute the edge frequency of edges.As the edges are cut according to the average edge frequency of all edges,the retention probability that an optimal Hamiltonian cycle edge is derived based on the constructed binomial distributions.Given Knof a traveling salesman problem,there are four steps for eliminating edges.Firstly,a finite number of quadrilaterals containing each edge are chosen.Secondly,the shortest path in the optimal cycle of every selected quadrilateral is used to compute the edge frequency.Thirdly,5/6 of edges having the smallest edge frequencies are cut.In the last step,some edges are added for vertices of degree below 2 according to the edge frequency.Experiments illustrate that the preserved edges occupy 1/6 of the total edges.Moreover,the computation time of the exact algorithms for the traveling salesman problem on the remaining graphs is reduced to some extent.

Key words: Cutting edge method, Edge frequency, Optimal cycles of quadrilaterals, Shortest path, Traveling salesman problem