The x-and-y-axes travelling salesman problem

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.

MoreLess

Year of publication:	2012
Authors:	Çela, Eranda ; Deineko, Vladimir ; Woeginger, Gerhard J.
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 223.2012, 2, p. 333-345
Publisher:	Elsevier
Subject:	Combinatorial optimization \| Polynomial-time algorithm \| Computational complexity \| Euclidean travelling salesman problem

Online Resource

Check full text access |

More access options

Check Google Scholar

In libraries world-wide (WorldCat)

In German libraries (KVK)

subito order

I need help

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10011052749