Research Paper | Mathematics | India | Volume 3 Issue 5, May 2014
Weight Constrained Travelling Salesman Problem on Halin Graphs
Dharmananda Gahir
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 Cite this Article?
Dharmananda Gahir, "Weight Constrained Travelling Salesman Problem on Halin Graphs", International Journal of Science and Research (IJSR), https://www.ijsr.net/search_index_results_paperid.php?id=20132158, Volume 3 Issue 5, May 2014, 1473 - 1480
43 PDF Views | 34 PDF Downloads
Similar Articles with Keyword 'Travelling Salesman Problem'
Research Paper, Mathematics, India, Volume 3 Issue 5, May 2014
Pages: 1473 - 1480Weight Constrained Travelling Salesman Problem on Halin Graphs
Dharmananda Gahir
Research Paper, Mathematics, India, Volume 3 Issue 12, December 2014
Pages: 184 - 186Travelling Salesman Problem (TSP) Using Fuzzy Quantifier
G. Nirmala, R. Anju
Research Paper, Mathematics, India, Volume 4 Issue 5, May 2015
Pages: 2258 - 2260A New Approach to Solve Fuzzy Travelling Salesman Problems by using Ranking Functions
Dr. S. Chandrasekaran, G. Kokila, Junu Saju
Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014
Pages: 315 - 317A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs
Dharamananada Gahir
Similar Articles with Keyword 'Halin graph'
Research Paper, Mathematics, India, Volume 3 Issue 5, May 2014
Pages: 1473 - 1480Weight Constrained Travelling Salesman Problem on Halin Graphs
Dharmananda Gahir
Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014
Pages: 315 - 317A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs
Dharamananada Gahir
Similar Articles with Keyword 'NP-Complete'
Research Paper, Mathematics, India, Volume 4 Issue 4, April 2015
Pages: 2164 - 2166R-Restricted Steiner Problem is NP-Complete
Dr. G. Nirmala, C. Sujatha
Research Paper, Mathematics, India, Volume 3 Issue 5, May 2014
Pages: 1473 - 1480Weight Constrained Travelling Salesman Problem on Halin Graphs
Dharmananda Gahir
Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014
Pages: 315 - 317A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs
Dharamananada Gahir
Similar Articles with Keyword 'Approximation scheme'
Research Paper, Mathematics, India, Volume 3 Issue 5, May 2014
Pages: 1473 - 1480Weight Constrained Travelling Salesman Problem on Halin Graphs
Dharmananda Gahir
Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014
Pages: 315 - 317A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs
Dharamananada Gahir