Downloads: 131 | Views: 353 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1
Research Paper | Mathematics | India | Volume 3 Issue 6, June 2014 | Rating: 6.3 / 10
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