@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.