A Fully Polynomial Time Approximation Scheme for Weight Constrained BTSP with Two Linear Constraints on Halin Graphs
International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
www.ijsr.net | Open Access | Fully Refereed | Peer Reviewed International Journal

ISSN: 2319-7064


Amazon Sale


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

Share this Article

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

78 PDF Views | 69 PDF Downloads

Download Article PDF


Amazon Sale


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