Downloads: 104
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
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 - 1110Hamiltonian Cycles and Travelling Salesfolk
Downloads: 126
Research Paper, Mathematics, India, Volume 3 Issue 12, December 2014
Pages: 184 - 186