Downloads: 130
Research Paper | Mathematics | India | Volume 3 Issue 6, June 2014
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
Similar Articles with Keyword 'Travelling'
Downloads: 1 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1
Research Paper, Mathematics, Spain, Volume 12 Issue 3, March 2023
Pages: 1089 - 1110Hamiltonian Cycles and Travelling Salesfolk
Downloads: 32
Research Paper, Mathematics, Iraq, Volume 5 Issue 11, November 2016
Pages: 1971 - 1974Exact Solutions for the Mikhailov-Shabat Equation, and Classical Boussinesq Equation by Tan-Cot Method
Anwar Ja'afar Mohamad Jawad | Syeda Naima Hassan