Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Abstract: We prove that the Weight Constrained Travelling Salesman Problem is NP- Complete by polynomially transforming the 0-1 Knapsack Problem to it and vice-versa. We present a pseudo-polynomial time algorithm for computing a weight constrained minimum cost Hamilton cycle in a Halin graph and then present a fully polynomial time approximation scheme for this NP-hard problem.

Keywords: Travelling Salesman Problem, Halin graph, NP-Complete, Approximation scheme, pseudo-polynomial time algorithm

How to Cite?: Dharmananda Gahir, "Weight Constrained Travelling Salesman Problem on Halin Graphs", Volume 3 Issue 5, May 2014, International Journal of Science and Research (IJSR), Pages: 1473-1480, https://www.ijsr.net/getabstract.php?paperid=20132158, DOI: https://dx.doi.org/10.21275/20132158