An approximate method to compute a sparse graph for traveling salesman problem

作者：

Highlights：

• The foundation of frequency graph is given for travelling salesman problem.

• The frequency graph is computed with the OP4s and time complexity is O(n4).

• The frequency threshold is derived to make the frequency graph sparse.

• The experiments show the search space of the best solution is reduced a lot.

摘要

•The foundation of frequency graph is given for travelling salesman problem.•The frequency graph is computed with the OP4s and time complexity is O(n4).•The frequency threshold is derived to make the frequency graph sparse.•The experiments show the search space of the best solution is reduced a lot.

论文关键词：Traveling salesman problem,Optimal k-vertex path,Frequency graph,Frequency threshold,Sparse graph

论文评审过程：Available online 2 March 2015.

论文官网地址：https://doi.org/10.1016/j.eswa.2015.02.037