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 | Views: 259

Research Paper | Mathematics | India | Volume 3 Issue 5, May 2014 | Popularity: 6.1 / 10


     

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



Make Sure to Disable the Pop-Up Blocker of Web Browser




Text copied to Clipboard!
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/getabstract.php?paperid=20132158, DOI: https://www.doi.org/10.21275/20132158



Similar Articles

Downloads: 2 | 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

Share this Article

Downloads: 104

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

Downloads: 126

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

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

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

Downloads: 139

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
Top