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

被引：20
|
作者：
DEINEKO, VG
VANDAL, R
ROTE, G
机构：
[1] GRAZ TECH UNIV,INST MATH,STEYRERGASSE 30,A-8010 GRAZ,AUSTRIA
[2] DNEPROPETROVSK UNIV,DEPT APPL MATH,DNEPROPETROVSK 320625,UKRAINE
[3] UNIV HEIDELBERG,RECHENZENTRUM,INTERDISZIPLINARES ZENTRUM WISSENSCHAFTLICHES RECHNEN,D-69120 HEIDELBERG,GERMANY
来源：
INFORMATION PROCESSING LETTERS | 1994年 / 51卷 / 03期
关键词：
EUCLIDEAN TRAVELING SALESMAN PROBLEM; SHORTEST PATH; WELL-SOLVABLE CASE; POLYNOMIAL TIME ALGORITHM;
D O I：
10.1016/0020-0190(94)00071-9
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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 cities, and the other m cities lie on a line segment inside this convex hull by an algorithm which needs O(mn) time and O(n) space.
引用
收藏
页码：141 / 148
页数：8
相关论文
共 50 条
12345