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

How to Download this Article?

Type Your Valid Email Address below to Receive the Article PDF Link

Verification Code will appear in 2 Seconds ... Wait

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

Similar Articles with Keyword 'Travelling'

Hamiltonian Cycles and Travelling Salesfolk

Exact Solutions for the Mikhailov-Shabat Equation, and Classical Boussinesq Equation by Tan-Cot Method