@article{ART001832446},
author={Sang-Un, Lee},
title={A Polynomial Time Algorithm of a Traveling Salesman Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2013},
volume={18},
number={12},
pages={75-82}
TY - JOUR
AU - Sang-Un, Lee
TI - A Polynomial Time Algorithm of a Traveling Salesman Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2013
VL - 18
IS - 12
PB - The Korean Society Of Computer And Information
SP - 75
EP - 82
SN - 1598-849X
AB - This paper proposes a O(n²) polynomial time algorithm to obtain optimal solution for Traveling Salesman problem that is a NP-complete because polynomial time algorithm has been not known yet. The biggest problem in a large-scale Traveling Salesman problem is the fact that the amount of data to be processed is n ×n, and thus as n increases, the data increases by multifold.
Therefore, this paper proposes a methodology by which the data amount is first reduced to approximately n/2. Then, it seeks a bi-directional route at a random point. The proposed algorithm has proved to be successful in obtaining the optimal solutions with O(n²) time complexity when applied to TSP-1 with 26 European cities and TSP-2 with 46 cities of the USA. It could therefore be applied as a generalized algorithm for TSP.
KW - CTraveling Salesman Problem;Exhaustive Search Method;Edge Exchange Method;Data Reduction
DO -
UR -
ER -
Sang-Un, Lee. (2013). A Polynomial Time Algorithm of a Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 18(12), 75-82.
Sang-Un, Lee. 2013, "A Polynomial Time Algorithm of a Traveling Salesman Problem", Journal of The Korea Society of Computer and Information, vol.18, no.12 pp.75-82.
Sang-Un, Lee "A Polynomial Time Algorithm of a Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 18.12 pp.75-82 (2013) : 75.
Sang-Un, Lee. A Polynomial Time Algorithm of a Traveling Salesman Problem. 2013; 18(12), 75-82.
Sang-Un, Lee. "A Polynomial Time Algorithm of a Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 18, no.12 (2013) : 75-82.
Sang-Un, Lee. A Polynomial Time Algorithm of a Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 18(12), 75-82.
Sang-Un, Lee. A Polynomial Time Algorithm of a Traveling Salesman Problem. Journal of The Korea Society of Computer and Information. 2013; 18(12) 75-82.
Sang-Un, Lee. A Polynomial Time Algorithm of a Traveling Salesman Problem. 2013; 18(12), 75-82.
Sang-Un, Lee. "A Polynomial Time Algorithm of a Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 18, no.12 (2013) : 75-82.
