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.