The x-and-y-axes travelling salesman problem

E. Çela, V.G. Deineko, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)333-345
JournalEuropean Journal of Operational Research
Volume223
Issue number2
DOIs
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'The x-and-y-axes travelling salesman problem'. Together they form a unique fingerprint.

  • Cite this