DocumentCode :
688147
Title :
A Representation Model for TSP
Author :
Yong Wang
Author_Institution :
Sch. of Renewable Energy, North China Electr. Power Univ., Beijing, China
fYear :
2013
fDate :
13-15 Nov. 2013
Firstpage :
204
Lastpage :
209
Abstract :
Traveling salesman problem (TSP) has been proven to be NP-complete and it is regarded for more than half a century. It is often represented as a weighted graph whereas the weighted graph cannot provide enough heuristic information for TSP. We do not know which edges belong to the best solution according to the edges´ weights. Here the frequency graph is introduced as a novel representation model for TSP. The frequency graph includes the law to connect the edges into the optimal Hamiltonian cycle (OHC). Based on the frequency graph, a sparse graph is computed and the search space of the OHC is reduced. Three steps are necessary to convert a complete weighted graph into a sparse graph with small number of edges. The frequency graph is computed with a set of local optimal Hamiltonian paths (LOHPs) at first. A sparse graph is computed according to a defined frequency threshold at the second step. A sparser graph is computed with the former sparse graph at the third step. The average degree of the final sparse graph is bounded to a small number and the search space of TSP is reduced. At last, the representation model is verified with several TSP instances with known optimal solutions.
Keywords :
computational complexity; graph theory; travelling salesman problems; LOHP; NP-complete problem; OHC; TSP; frequency graph; local optimal Hamiltonian paths; optimal Hamiltonian cycle; representation model; sparse graph; sparser graph; traveling salesman problem; weighted graph; Algorithm design and analysis; Approximation algorithms; Approximation methods; Cities and towns; Complexity theory; Computational modeling; Time-frequency analysis; Traveling salesman problem; frequency graph; frequency threshold; sparse graph;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing (HPCC_EUC), 2013 IEEE 10th International Conference on
Conference_Location :
Zhangjiajie
Type :
conf
DOI :
10.1109/HPCC.and.EUC.2013.38
Filename :
6831920
Link To Document :
بازگشت