Share Your Research, Maximize Your Social Impacts
Weight Constrained Travelling Salesman Problem on Halin Graphs
Journal: International Journal of Science and Research (IJSR) (Vol.3, No. 5)Publication Date: 2014-05-15
Authors : Dharmananda Gahir;
Page : 1473-1480
Keywords : Travelling Salesman Problem; Halin graph; NP-Complete; Approximation scheme; pseudo-polynomial time algorithm;
Source : Download
Find it from : Google Scholar
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.
Other Latest Articles
- Improvement in Plant Layout Using Material Handling Technique
- Survival Analysis of HIV Infected People on Antiretroviral Therapy at Mizan-Aman General Hospital, Southwest Ethiopia
- Using Peer to Peer Approach of Distributed Systems to Design a Chat Room Application
- Activities of the Boko Haram Sect as Threat to Nigeria Security
- Cluster Based Efficient Location Aware - Source Multicast Routing Approach for Wireless Sensor Networks
Last modified: 2014-07-03 16:36:09