A LINEAR-TIME ALGORITHM FOR THE BOTTLENECK TRAVELING SALESMAN PROBLEMON A HALIN GRAPH

Authors
PHILLIPS JM PUNNEN AP KABADI SN
Citation
Jm. Phillips et al., A LINEAR-TIME ALGORITHM FOR THE BOTTLENECK TRAVELING SALESMAN PROBLEMON A HALIN GRAPH, Information processing letters, 67(2), 1998, pp. 105-110
Citations number
8
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
67
Issue
2
Year of publication
1998
Pages
105 - 110
Database
ISI
SICI code
0020-0190(1998)67:2<105:ALAFTB>2.0.ZU;2-A
Abstract
We provide a linear time algorithm to solve the bottleneck traveling s alesman problem on a Halin graph. This improves the O(n log n) time bo und obtained by the binary search version of the threshold algorithm. (C) 1998 Elsevier Science B.V. All rights reserved.