THE CONVEX-HULL-AND-LINE TRAVELING SALESMAN PROBLEM - A SOLVABLE CASE

Authors
DEINEKO VG VANDAL R ROTE G
Citation
Vg. Deineko et al., THE CONVEX-HULL-AND-LINE TRAVELING SALESMAN PROBLEM - A SOLVABLE CASE, Information processing letters, 51(3), 1994, pp. 141-148
Citations number
6
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
51
Issue
3
Year of publication
1994
Pages
141 - 148
Database
ISI
SICI code
0020-0190(1994)51:3<141:TCTSP->2.0.ZU;2-C
Abstract
We solve the special case of the Euclidean Traveling Salesman Problem where n - m cities lie on the boundary of the convex hull of all n cit ies, and the other m cities lie on a line segment inside this convex h ull by an algorithm which needs O(mn) time and O(n) space.