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

Research Paper | Mathematics | India | Volume 3 Issue 6, June 2014 | Popularity: 6.3 / 10

Rate This Article!      

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

Dharamananada Gahir

Abstract: In this paper we show that the weight constrained version of BTSP i. e. WCBTSP on a Halin graph with n nodes can be solved in O (nlogn) time. We also show that WCBTSP with two linear constraints on a Halin graph can be solved in O (n (W1+1) 2 logn) time; where W1 denotes the first right hand side constant.

Keywords: Bottleneck Travelling Salesman Problem, Halin graph, NP-Complete, Threshold algorithm, polynomial time approximation scheme

Edition: Volume 3 Issue 6, June 2014

Pages: 315 - 317

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

Click to Cite this Article

Similar Articles