Downloads: 139
Research Paper | Mathematics | Volume 3 Issue 6, June 2014 | Pages: 315 - 317 | India
A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs
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
How to Cite?: Dharamananada Gahir, "A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs", Volume 3 Issue 6, June 2014, International Journal of Science and Research (IJSR), Pages: 315-317, https://www.ijsr.net/getabstract.php?paperid=2014131, DOI: https://dx.doi.org/10.21275/2014131