International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
www.ijsr.net | Most Trusted Research Journal Since Year 2012

ISSN: 2319-7064



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

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 Cite this Article?

Dharamananada Gahir, "A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs", International Journal of Science and Research (IJSR), https://www.ijsr.net/search_index_results_paperid.php?id=2014131, Volume 3 Issue 6, June 2014, 315 - 317

42 PDF Views | 41 PDF Downloads

Download Article PDF



Similar Articles with Keyword 'Halin graph'

Research Paper, Mathematics, India, Volume 3 Issue 5, May 2014

Pages: 1473 - 1480

Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Share this article

Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014

Pages: 315 - 317

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

Dharamananada Gahir

Share this article



Similar Articles with Keyword 'NP-Complete'

Research Paper, Mathematics, India, Volume 4 Issue 4, April 2015

Pages: 2164 - 2166

R-Restricted Steiner Problem is NP-Complete

Dr. G. Nirmala, C. Sujatha

Share this article

Research Paper, Mathematics, India, Volume 3 Issue 5, May 2014

Pages: 1473 - 1480

Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Share this article

Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014

Pages: 315 - 317

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

Dharamananada Gahir

Share this article



Similar Articles with Keyword 'polynomial time approximation scheme'

Research Paper, Mathematics, India, Volume 3 Issue 5, May 2014

Pages: 1473 - 1480

Weight Constrained Travelling Salesman Problem on Halin Graphs

Dharmananda Gahir

Share this article

Research Paper, Mathematics, India, Volume 3 Issue 6, June 2014

Pages: 315 - 317

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

Dharamananada Gahir

Share this article
Top