Çela, Eranda, Deineko, Vladimir G. and Woeginger, Gerhard J. (2012) The x-and-y-axes travelling salesman problem. European Journal of Operational Research, 223 (2). pp. 333-345. doi:10.1016/j.ejor.2012.06.036 ISSN 0377-2217.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

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.

Highlights
- A special solvable case of the travelling salesman problem (TSP) is considered. - All cities in this TSP are situated on the x-and-y-axes of the Euclidean plane. - The problem remained open since 1980. - The running time of our algorithm is quadratic in the number of cities.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School
Journal or Publication Title:	European Journal of Operational Research
Publisher:	Elsevier Science BV
ISSN:	0377-2217
Official Date:	1 December 2012
Dates:	Date Event 1 December 2012 Published
Volume:	223
Number:	2
Page Range:	pp. 333-345
DOI:	10.1016/j.ejor.2012.06.036
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item