International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Call for Papers | Fully Refereed | Open Access | Double Blind Peer Reviewed

ISSN: 2319-7064


Downloads: 104 | Views: 165

Research Paper | Mathematics | India | Volume 3 Issue 5, May 2014


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


Edition: Volume 3 Issue 5, May 2014,


Pages: 1473 - 1480


How to Download this Article?

Type Your Valid Email Address below to Receive the Article PDF Link


Verification Code will appear in 2 Seconds ... Wait

Top