Polynomial Reduction of TSP to Freely Open-loop TSP - Abdulrazaq, Muhammad Bashir; Tahir, Yusuf Suleiman; Sha'Aban, Suleiman; Jibia, Muhammed Sani (Institute of Electrical and Electronics Engineers Inc., 2019)
Travelling Salesman Problem (TSP) is one of the earliest combinatorial problem that is identified to be NP-hard problem. It is a problem that seeks to find the shortest possible route in a graph problem which passes through all nodes only once and return to the starting point. A variant of TSP is the Freely Open-loop TSP (FOTSP) which seeks to find the shortest route in the graph without having to return to starting point and with no specific starting or end node. In this paper, a reduction of polynomial complexity for TSP problem into FOTSP is presented and vice versa. This reduction proves that FOTSP is also NP-complete just as TSP. © 2019 IEEE.
2nd International Conference of the IEEE Nigeria Computer Chapter, NigeriaComputConf 2019 -- 2019-10-14 through 2019-10-17 -- Zaria -- 156683
Keywords: FOTSP; NP-complete; NP-hard; Polynomial Reduction; Travelling Salesman Problem