International Journal of Science and Research (IJSR)

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

ISSN: 2319-7064




Downloads: 104 | Views: 119

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 Email Address below to Download the Article PDF


How to Cite this Article?

Dharmananda Gahir, "Weight Constrained Travelling Salesman Problem on Halin Graphs", International Journal of Science and Research (IJSR), Volume 3 Issue 5, May 2014, pp. 1473-1480, https://www.ijsr.net/get_abstract.php?paper_id=20132158



Similar Articles with Keyword 'Travelling Salesman Problem'

Downloads: 1 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1

Research Paper, Mathematics, Spain, Volume 12 Issue 3, March 2023

Pages: 1089 - 1110

Hamiltonian Cycles and Travelling Salesfolk

Alberto Gomez Gomez [2]

Share this Article

Downloads: 126

Research Paper, Mathematics, India, Volume 3 Issue 12, December 2014

Pages: 184 - 186

Travelling Salesman Problem (TSP) Using Fuzzy Quantifier

G. Nirmala [7] | R. Anju [8]

Share this Article



Top