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

India | Mathematics | Volume 3 Issue 5, May 2014 | Pages: 1473 - 1480


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



Citation copied to Clipboard!
Dharmananda Gahir, "Weight Constrained Travelling Salesman Problem on Halin Graphs." International Journal of Science and Research (IJSR), vol. 3, no. 5, 2014, pp. 1473-1480, https://www.ijsr.net/getabstract.php?paperid=20132158, DOI: https://www.doi.org/10.21275/20132158


Top