Weight Constrained Travelling Salesman Problem on Halin Graphs
International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
www.ijsr.net | Most Trusted Research Journal Since Year 2012

ISSN: 2319-7064



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

Share this Article

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

Download Article PDF



Similar Articles with Keyword 'Travelling Salesman Problem'

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

Pages: 1473 - 1480

Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Share this Article

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

Pages: 184 - 186

Travelling Salesman Problem (TSP) Using Fuzzy Quantifier

G. Nirmala, R. Anju

Share this Article

Research Paper, Mathematics, India, Volume 4 Issue 5, May 2015

Pages: 2258 - 2260

A New Approach to Solve Fuzzy Travelling Salesman Problems by using Ranking Functions

Dr. S. Chandrasekaran, G. Kokila, Junu Saju

Share this Article

Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014

Pages: 315 - 317

A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs

Dharamananada Gahir

Share this Article

Similar Articles with Keyword 'Halin graph'

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

Pages: 1473 - 1480

Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Share this Article

Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014

Pages: 315 - 317

A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs

Dharamananada Gahir

Share this Article

Similar Articles with Keyword 'NP-Complete'

Research Paper, Mathematics, India, Volume 4 Issue 4, April 2015

Pages: 2164 - 2166

R-Restricted Steiner Problem is NP-Complete

Dr. G. Nirmala, C. Sujatha

Share this Article

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

Pages: 1473 - 1480

Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Share this Article

Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014

Pages: 315 - 317

A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs

Dharamananada Gahir

Share this Article

Similar Articles with Keyword 'Approximation scheme'

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

Pages: 1473 - 1480

Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Share this Article

Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014

Pages: 315 - 317

A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs

Dharamananada Gahir

Share this Article
Top