The x-and-y-axes travelling salesman problem

被引：5

作者：

Cela, Eranda ^{[3
]}

Deineko, Vladimir ^{[1
]}

Woeginger, Gerhard J. ^{[2
]}

机构：

[1] Warwick Business Sch, Coventry CV4 7AL, W Midlands, England

[2] TU Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands

[3] Graz Univ Technol, Inst Optimierung & Diskrete Math, A-8010 Graz, Austria

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2012年 / 223卷 / 02期

基金：

英国工程与自然科学研究理事会;

关键词：

Combinatorial optimization; Polynomial-time algorithm; Computational complexity; Euclidean travelling salesman problem; TSP; TOURS; PLANE;

D O I：

10.1016/j.ejor.2012.06.036

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show that this problem can be solved in polynomial time. The running time of the resulting algorithm is quadratic in the number of cities. (C) 2012 Elsevier By. All rights reserved.

引用

页码：333 / 345

页数：13

共 19 条

[1] Euclidean TSP between two nested convex obstacles [J].